1 solutions
-
1Bullet LV 4 MOD @ 2024-08-24 15:57:05
Code(C++) :
#include<bits/stdc++.h> using namespace std; const long long M=3e5+10,MOD=1000000000; typedef long long ll; vector<int>edge[M]; int level[M]; int d[M]; ll sum[M]; int arr[M]; void dfs1(int x,int p){ for(int u:edge[x]){ if(u!=p){ d[u]=d[x]+1; dfs1(u,x); } } } void dfs(int x,int p){ for(int u:edge[x]){ if(u!=p){ d[u]=d[x]+1; dfs(u,x); } } level[p]+=level[x]; sum[p]+=sum[x]+(2*min(1,level[x])); } void clear_edge(int n){ for(int i=0;i<=n;i++){ edge[i].clear(); sum[i]=0; level[i]=0; d[i]=0; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int t=1; cin>>t; while(t--){ int n; cin>>n; int cnt=0; clear_edge(n); int node=1; for(int i=1;i<=n;i++){ cin>>level[i]; cnt+=level[i]; arr[i]=level[i]; if(arr[i])node=i; } for(int i=1;i<n;i++){ int x,y; cin>>x>>y; edge[x].push_back(y); edge[y].push_back(x); } if(cnt<=1){ cout<<0<<"\n"; continue; } dfs(node,0); int cur=1; int mx_dis=0; for(int i=1;i<=n;i++){ if(mx_dis<d[i] && arr[i]){ mx_dis=d[i]; cur=i; } d[i]=0; } dfs1(cur,0); int maximum_dis=0; for(int i=1;i<=n;i++)if(arr[i])maximum_dis=max(maximum_dis,d[i]); cout<<sum[node]-maximum_dis<<"\n"; } return 0; }
- 1
Information
- ID
- 1078
- Difficulty
- 7
- Category
- Graph_Theory | DFS , BFS , Shortest_Path Click to Show
- Tags
- # Submissions
- 49
- Accepted
- 10
- Accepted Ratio
- 20%
- Uploaded By