Problem Solution

1 solutions

  • 1
    @ 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