Help , Subtree size sum calculation by taking each vertex as a root (Graph Problem 8 )

Yesterday, I gave the contest “Devil code” on gfg ,
so here is one of the toughest question in the contest -

https://practice.geeksforgeeks.org/problems/defeat-the-night-crawler/1

What I thought is ,we have to find max sum subtree by taking each vertex as a node, and print max value but it will be N2 , so it will give TLE.

void SubtreeSize_DFS(vi adj[] , lli src , vi &sub_size , vbool &vis )
{
    vis[src] =1;
    sub_size[src] = 1;
    
    for(auto xt : adj[src])
    {
        if(!vis[xt])
        {
            SubtreeSize_DFS(adj , xt,sub_size , vis);
            sub_size[src] += sub_size[xt];
        }
    }
}


int main(){
fastio
lli t=1;
cin>>t;
chandan2();
while(t--) {
    lli n;
    cin>>n;
    vi adj[n+1];
    lli maxi = -1;
    lli x,y;
    loop(i,n-1){
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(lli i=1;i<=n;i++)
    {
        vi arr(n+1,0);
        lli sum= 0 ;
        vbool vis(n+1 , false);
        SubtreeSize_DFS(adj , i , arr , vis);
        FOR(i,1,n+1)
            sum+=arr[i];
        
        maxi = max(maxi , sum);
            
    }
    
    print(maxi);
  }
return 0;
}

How can I optimize this, please explain approach, technique, algorithm, and if this is something which I don’t know like some other higher concept then please suggest resources too.

@carre @galencolin @ssjgz @l_returns @aneee004 @everule1 @aryan12 @bohdan

Think of what happens calculate from i and then go to j when i and j are adjacent.j stops being a subtree of i, and the rest of i becomes a subtree of j. Using that you can calculate it quickly.

Code
int maxPoints(vector<vector<int>> &edges){
    int n = edges.size() + 1;
    vector<vector<int>> adj(n);
    for(const auto &edge : edges){
        adj[edge[0]-1].pb(edge[1]-1);
        adj[edge[1]-1].pb(edge[0]-1);
    }
    vector<int> sz(n,1);
    vector<int> path;
    path.reserve(n<<1);
    ll sum = 0;
    function<void(int,int)> dfs = [&](int u,int par){
        path.pb(u);
        for(const auto &x : adj[u]){
            if(x==par){
                continue;
            }
            dfs(x,u);
            path.pb(u);
            sz[u]+=sz[x];
        }
        sum+=sz[u];
    };
    dfs(0,-1);
    ll ans = sum;
    for(int i=1;i<path.size();i++){
        int x = path[i-1], y = path[i];
        sum-=sz[x]+sz[y];
        sz[x]-=sz[y];
        sz[y]+=sz[x];
        sum+=sz[x] + sz[y];
        ans = max(ans, sum);
    }
    return ans;
}

Also known as “Rerooting”

1 Like