PROBLEM LINKS:
Author and Editorialist: Aakash Mehta
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Trees, LCA, Centroid.
PROBLEM:
On a weighted tree, for all the nodes of the tree, we need to calculate total maximum distance possible that can be covered such that every node goes to some other node.
EXPLANATION:
Consider the distance between two nodes as:
dis(u,v) = droot(u) + droot(v) - 2*droot(lca of u,v);
Here dis(u,v) denotes the distance between two nodes u,v. droot(u) denotes the distance of the node u from the root. Lca of u,v denotes the lowest common ancestor of nodes u,v.
Now let’s assume an array of n size, such that the array value at ith index denotes the node to which the ith index node travelled. We need summation of the distances, which is :
\displaystyle \sum ^{N}_{i=1} dis( i,arr[ i])
\displaystyle \sum ^{N}_{i=1} dis( i,arr[ i]) = \displaystyle \sum ^{N}_{i=1}( \ droot( i) \ +\ droot( arr[ i]) \ -\ 2*droot( \ LCA\ of\ i,arr[ i] \ )
= \displaystyle 2*\sum ^{N}_{i=1} \ droot( i) \ -\ 2*\sum ^{N}_{i=1} droot( LCA\ of\ i,\ arr[ i\})
Now, the question comes to choosing such a root that LCA of all i’s and arr[i]'s is minimum possible. What minimum value could you think of?
It’s zero. The distance of LCA from the root of all the i’s and arr[i]'s will be zero if their LCA turns out to be the root of the tree. But does such node exist which could be regarded as root of the tree, such that we could make such pairs that all of them have their LCA as this root only?
The answer is YES. That node would be Centroid of the tree. You can read more about it here: -
Now the solution just simplifies into finding the centroid and then computing \displaystyle 2*\sum ^{N}_{i=1} \ droot( i).
SOLUTION: -
Author Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define deb(x) cout<<#x<<" "<<x<<endl
#define sc(ar,n) for(int pen=0;pen<n;pen++){ cin>>ar[pen];}
#define pr(ar) for(int pen=0;pen<sizeof(ar)/8;pen++){ cout<<ar[pen]<<" ";} cout<<endl;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
vector <pair<int,int>> vt[100001];
int is_cent[100001];
int dp[100001];
int vis[100001];
int sz[100001];
int n;
void dfs(int u){
vis[u]=1;
sz[u]++;
for(auto it=vt[u].begin();it!=vt[u].end();it++){
int a=it->first;
int b=it->second;
if(vis[a]!=1){
dfs(a);
sz[u]+=sz[a];
if(sz[a]>n/2){
is_cent[u]=1;
}
dp[u]+=dp[a]+b*sz[a];
}
}
if(n-sz[u]>n/2){
is_cent[u]=1;
}
}
signed main()
{
// int n;
cin>>n;
for(int i=1;i<=n;i++){
vis[i]=0;
dp[i]=0;
sz[i]=0;
vt[i].clear();
is_cent[i]=0;
}
for(int i=0;i<n-1;i++){
int u,v,w;
cin>>u>>v>>w;
vt[u].push_back(make_pair(v,w));
vt[v].push_back(make_pair(u,w));
}
int u=1;
dfs(1);
for(int i=1;i<=n;i++){
if(is_cent[i]==0){
u=i;
break;
}
}
for(int i=1;i<=n;i++){
dp[i]=0;
sz[i]=0;
vis[i]=0;
}
dfs(u);
cout<<2*dp[u]<<endl;
}If you have any doubts regarding the problem, feel free to ask them in the comments.
