 # 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 -

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;

{
if(!vis[xt])
{
sub_size[src] += sub_size[xt];
}
}
}

int main(){
fastio
lli t=1;
cin>>t;
chandan2();
while(t--) {
lli n;
cin>>n;
lli maxi = -1;
lli x,y;
loop(i,n-1){
cin>>x>>y;
}
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.

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;
for(const auto &edge : edges){
}
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);
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