Advertisement
Mysakure

Untitled

Oct 21st, 2019
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. /**
  2.  *    author:  MySakure
  3.  *    created: 21.10.2019 11:22:49      
  4. **/
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. #define int long long
  8. const int maxn=1e6+10;
  9. const int inf=1e18;
  10. int dp[maxn][2],t,n,v[maxn],ans;
  11. vector<int>g[maxn];
  12. //0 最大值
  13. //1 最小值
  14. void dfs(int u,int fa){
  15.     dp[u][0]=min(dp[u][0],1-v[u]);
  16.     dp[u][1]=min(dp[u][1],1+v[u]);
  17.     if(fa!=-1){
  18.         dp[u][0]=min(dp[u][0],dp[fa][0]+1);
  19.         dp[u][1]=min(dp[u][1],dp[fa][1]+1);
  20.     }
  21.     for(int i=0;i<signed(g[u].size());++i){
  22.         int v=g[u][i];
  23.         if(v==fa)continue;
  24.         dfs(v,u);
  25.         ans=min(ans,dp[v][0]+dp[u][1]);
  26.         ans=min(ans,dp[v][1]+dp[u][0]);
  27.         dp[u][0]=min(dp[u][0],dp[v][0]+1);
  28.         dp[u][1]=min(dp[u][1],dp[v][1]+1);
  29.     }
  30. }
  31. signed main() {
  32.     ios::sync_with_stdio(false);
  33.     cin.tie(NULL);
  34. #ifdef mysakure
  35.     freopen("in.txt","r",stdin);
  36.     freopen("ans1.txt","w",stdout);
  37. #endif
  38.     cin>>t;
  39.     while(t--){
  40.         cin>>n;
  41.         for(int i=1;i<=n;++i)cin>>v[i];
  42.         for(int i=1;i<=n;++i)g[i].clear();
  43.         for(int i=1;i<n;++i){
  44.             int a,b;
  45.             cin>>a>>b;
  46.             g[a].push_back(b);
  47.             g[b].push_back(a);
  48.         }
  49.         for(int i=1;i<=n;++i){
  50.             dp[i][1]=dp[i][0]=inf;
  51.         }
  52.         ans=1;
  53.         dfs(1,-1);
  54.         cout<<ans<<endl;
  55.     }
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement