Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * author: MySakure
- * created: 21.10.2019 11:22:49
- **/
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- const int maxn=1e6+10;
- const int inf=1e18;
- int dp[maxn][2],t,n,v[maxn],ans;
- vector<int>g[maxn];
- //0 最大值
- //1 最小值
- void dfs(int u,int fa){
- dp[u][0]=min(dp[u][0],1-v[u]);
- dp[u][1]=min(dp[u][1],1+v[u]);
- if(fa!=-1){
- dp[u][0]=min(dp[u][0],dp[fa][0]+1);
- dp[u][1]=min(dp[u][1],dp[fa][1]+1);
- }
- for(int i=0;i<signed(g[u].size());++i){
- int v=g[u][i];
- if(v==fa)continue;
- dfs(v,u);
- ans=min(ans,dp[v][0]+dp[u][1]);
- ans=min(ans,dp[v][1]+dp[u][0]);
- dp[u][0]=min(dp[u][0],dp[v][0]+1);
- dp[u][1]=min(dp[u][1],dp[v][1]+1);
- }
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- #ifdef mysakure
- freopen("in.txt","r",stdin);
- freopen("ans1.txt","w",stdout);
- #endif
- cin>>t;
- while(t--){
- cin>>n;
- for(int i=1;i<=n;++i)cin>>v[i];
- for(int i=1;i<=n;++i)g[i].clear();
- for(int i=1;i<n;++i){
- int a,b;
- cin>>a>>b;
- g[a].push_back(b);
- g[b].push_back(a);
- }
- for(int i=1;i<=n;++i){
- dp[i][1]=dp[i][0]=inf;
- }
- ans=1;
- dfs(1,-1);
- cout<<ans<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement