Description
傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。 在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。 整个地图是一个树结构，一共有n块空地，这些空地被n-1条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。 如果补给站在点u上，并且空地v上有dv个单位的军队，那么幽香每天就要花费dv×dist(u,v)的金钱来补给这些军队。由于幽香需要补给所有的军队，因此幽香总共就要花费为Sigma(Dv*dist(u，v),其中1<=V<=N)的代价。其中dist(u,v)表示u个v在树上的距离（唯一路径的权和）。 因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。
Input
Output
对于幽香的每个操作，输出操作完成以后，每天的最小花费，也即如果幽香选择最优的补给点进行补给时的花费。
Sample Input
1 2 1
2 3 1
2 4 1
1 5 1
2 6 1
2 7 1
5 8 1
7 9 1
1 10 1
3 1
2 1
8 1
3 1
4 1
Sample Output
1
4
5
6
HINT
第一道动态点分治的题，其实以前做过但是完全忘了，现在重新做一遍又有新的理解
首先这个题意是树上点权修改，询问带权重心。我们设$sum_u$表示$u$子树内的权值和，$sum_v$表示$v$子树内的权值和，如果要从$u$走到$v$，答案的变化量为$len(u,v)*(sum_u-sum_v-sum_v)$
即当$sum_u \le 2*sum_v$时，我们才能从$u$走到$v$，显然$v$点只会有一个，而且这个过程一定会停止
而如何快速求出每个点为根的花费以及如何快速支持修改，这里就可以考虑构建点分树了
我们知道点分治有一个性质，即原树上两点$p$和$q$两点之间的路径的第一个重心就是点分树上的$LCA$
这样我们爬一遍树，就可以求出$p$与其他点之间的信息了，每次修改也暴力爬树即可
代码：
1 #include<iostream> 2 #include<cstdio> 3 #define M 400010 4 #define ll long long 5 using namespace std; 6 struct point{int next,to,dis;}e[M<<1]; 7 //sumv[i]表示以i为根的子树权值和 8 //ans[i]表示以i为根的子树中所有节点到i结点dv*dis的和 9 //ans1[i]表示点分树中以i为根的子树中所有结点到i的父亲的dv*dis的和 10 int n,m,num,cnt,last,sum,root; 11 int head[M],deep[M],size[M],maxn[M]; 12 int fa[M],top[M],sz[M],f[M],son[M]; 13 ll sumv[M],ans1[M],ans[M],dist[M]; 14 bool vis[M]; 15 void add(int from,int to,int dis) 16 { 17 e[++num].next=head[from]; 18 e[num].to=to; 19 e[num].dis=dis; 20 head[from]=num; 21 } 22 void dfs(int x) 23 { 24 sz[x]=1; 25 for(int i=head[x];i;i=e[i].next) 26 { 27 int to=e[i].to; 28 if(sz[to]) continue; 29 deep[to]=deep[x]+1; 30 dist[to]=dist[x]+e[i].dis; 31 f[to]=x; 32 dfs(to); 33 sz[x]+=sz[to]; 34 if(sz[son[x]]<sz[to]) son[x]=to; 35 } 36 } 37 void dfs2(int x,int tp) 38 { 39 top[x]=tp; 40 if(son[x]) dfs2(son[x],tp); 41 for(int i=head[x];i;i=e[i].next) 42 { 43 int to=e[i].to; 44 if(to==f[x]||to==son[x]) continue; 45 dfs2(to,to); 46 } 47 } 48 int lca(int x,int y) 49 { 50 while(top[x]!=top[y]) 51 { 52 if(deep[top[x]]<deep[top[y]]) swap(x,y); 53 x=f[top[x]]; 54 } 55 if(deep[x]<deep[y]) return x; 56 else return y; 57 } 58 int dis(int x,int y) 59 { 60 int LCA=lca(x,y); 61 return dist[x]+dist[y]-2*dist[LCA]; 62 } 63 void getroot(int x,int fa) 64 { 65 size[x]=1; maxn[x]=0; 66 for(int i=head[x];i;i=e[i].next) 67 { 68 int to=e[i].to; 69 if(to==fa||vis[to]) continue; 70 getroot(to,x); 71 size[x]+=size[to]; 72 maxn[x]=max(maxn[x],size[to]); 73 } 74 maxn[x]=max(maxn[x],sum-size[x]); 75 if(maxn[x]<maxn[root]) root=x; 76 } 77 void work(int x) 78 { 79 vis[x]=true; 80 for(int i=head[x];i;i=e[i].next) 81 { 82 int to=e[i].to; 83 if(vis[to]) continue; 84 root=0,sum=size[to]; 85 getroot(to,0); fa[root]=x; 86 work(root); 87 } 88 } 89 void update(int x,int val) 90 { 91 sumv[x]+=val; 92 for(int i=x;fa[i];i=fa[i]) 93 { 94 ll d=dis(fa[i],x); 95 sumv[fa[i]]+=val; 96 ans1[i]+=val*d; 97 ans[fa[i]]+=val*d; 98 } 99 } 100 ll cal(int x) 101 { 102 ll ret=ans[x]; 103 for(int i=x;fa[i];i=fa[i]) 104 { 105 ll dt=dis(fa[i],x); 106 ret+=(ans[fa[i]]-ans1[i]);//去掉子树i 107 ret+=dt*(sumv[fa[i]]-sumv[i]);//重新计算子树i的贡献 108 } 109 return ret; 110 } 111 ll ask(int x) 112 { 113 ll K=cal(x); 114 for(int i=head[x];i;i=e[i].next) 115 { 116 int to=e[i].to; 117 ll tmp=cal(to); 118 if(tmp<K) return ask(to); 119 } 120 last=x; return K; 121 } 122 int main() 123 { 124 scanf("%d%d",&n,&m); 125 for(int i=1;i<=n-1;i++) 126 { 127 int x,y,z; 128 scanf("%d%d%d",&x,&y,&z); 129 add(x,y,z); add(y,x,z); 130 } 131 deep[1]=1; dfs(1); dfs2(1,1); 132 sum=maxn[0]=n; 133 getroot(1,0); 134 work(root); 135 last=1; 136 for(int i=1;i<=m;i++) 137 { 138 int x,y; 139 scanf("%d%d",&x,&y); 140 update(x,y); 141 printf("%lld\n",ask(last)); 142 } 143 return 0; 144 }