题目
题目描述
傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。
在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。 整个地图是一个树结构，一共有n块空地，这些空地被n-1条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。
在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。 如果补给站在点u上，并且空地v上有dv个单位的军队，那么幽香每天就要花费dv*dist(u,v)的金钱来补给这些军队。
由于幽香需要补给所有的军队，因此幽香总共就要花费为Sigma(Dv*dist(u，v),其中1<=V<=N)的代价。其中dist(u,v)表示u个v在树上的距离（唯一路径的权和）。
因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。
但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。
输入输出格式
输入格式：
第一行两个数n和Q分别表示树的点数和幽香操作的个数，其中点从1到n标号。 接下来n-1行，每行三个正整数a,b,c，表示a和b之间有一条边权为c的边。 接下来Q行，每行两个数u,e，表示幽香在点u上放了e单位个军队（如果e<0，就相当于是幽香在u上减少了|e|单位个军队，说白了就是du←du+e）。数据保证任何时刻每个点上的军队数量都是非负的。
输出格式：
对于幽香的每个操作，输出操作完成以后，每天的最小花费，也即如果幽香选择最优的补给点进行补给时的花费。
输入输出样例
输入样例#1：
10 5
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
输出样例#1：
0
1
4
5
6
说明
对于所有数据，1<=c<=1000, -1000<=e<=1000, n<=10^5, Q<=10^5 非常神奇的是，对于所有数据，这棵树上的点的度数都不超过20，且N，Q>=1
题解
发现题目就是要找整棵树的带权重心，并且这个重心有且只有一个
对于点分树上节点$x$维护$3$个值：子树中$dv$的和，子树中每个点到$x$的$dv\times dist$的和，子树中每个点到$x$在点分树上的父亲的$dv\times dist$的和
所以可以用$O(logn)$的时间求得出来某个点的答案，如果$x$的儿子中有点的答案小于$x$，说明这个儿子比$x$更接近带权重心，所以要进入那个点的子树求得答案
如果一步一步的求，每次的查询就会被卡成$O(nlogn)$的……
进入子树的时候，可以从子树的重心开始求解，这样复杂度就变成了$O({logn}^2)$的了，同时因为每次只改一个点，所以带权重心一般不会移动很远，这样可以从上一个查询的答案节点开始查询（小优化），最终复杂度$O(q\log^2n)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e5+5;
struct p{
int x,y,dis;
}c[MAX<<1];
int n,m,num=1,cnt,Sum,rt,Lat=1;
int h[MAX],id[MAX],_id[MAX<<1],__sum[MAX],f[MAX],d[MAX],siz[MAX],son[MAX],fa[MAX],top[MAX],D[MAX],_D[MAX],F[MAX];
LL sum[MAX],_sum[MAX];
bool use[MAX];
int read()
{
int x=0,fl=1;
char ch=getchar();
for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*fl;
}
void GET_ROOT(int x=1,int fa=0)
{
f[x]=0,siz[x]=1;
for(int i=h[x];i;i=c[i].x)
if((c[i].y^fa)&&(!use[c[i].y])) GET_ROOT(c[i].y,x),f[x]=max(f[x],siz[c[i].y]),siz[x]+=siz[c[i].y];
f[x]=max(f[x],Sum-siz[x]);
if(f[x]<f[rt]) rt=x;
}
void add(int x,int y,int dis)
{
c[++num]=(p){h[x],y,dis},h[x]=num;
c[++num]=(p){h[y],x,dis},h[y]=num;
}
void dfs(int x=rt)
{
use[x]=1;
int xsum=Sum;
for(int i=h[x];i;i=c[i].x)
if(!use[c[i].y])
{
if(siz[c[i].y]>siz[x]) Sum=xsum-siz[x];
else Sum=siz[c[i].y];
f[rt=0]=Sum,GET_ROOT(c[i].y,x),F[rt]=x,_id[i]=rt,_id[i^1]=x,dfs(rt);
}
}
void dfs_(int x=1,int F=0,int dis=0)
{
fa[x]=F,d[x]=d[F]+(siz[x]=1),D[x]=D[F]+dis;
for(int i=h[x];i;i=c[i].x)
if(c[i].y^F)
{
dfs_(c[i].y,x,c[i].dis),siz[x]+=siz[c[i].y];
if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
}
}
void dfs__(int x=1,int tp=1)
{
top[x]=tp,id[x]=++cnt;
if(!son[x]) return;
dfs__(son[x],tp);
for(int i=h[x];i;i=c[i].x)
if((c[i].y^fa[x])&&(c[i].y^son[x])) dfs__(c[i].y,c[i].y);
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=fa[top[x]];
}
return d[x]>d[y]?y:x;
}
int GET_DIS(int x,int y) {return D[x]+D[y]-(D[LCA(x,y)]<<1);}
LL GET_ANS(int x)
{
LL ans=sum[x];
for(int i=x,_d;F[i];i=F[i])
_d=GET_DIS(F[i],x),ans+=(sum[F[i]]-_sum[i])+1ll*_d*(__sum[F[i]]-__sum[i]);
return ans;
}
void change(int x,int D)
{
__sum[x]+=D;
for(int i=x,_d;F[i];i=F[i])
_d=GET_DIS(F[i],x),__sum[F[i]]+=D,_sum[i]+=1ll*_d*D,sum[F[i]]+=1ll*_d*D;
}
LL ask(int x=Lat)
{
LL s1=GET_ANS(x),s2;
for(int i=h[x];i;i=c[i].x)
if(_id[i])
{
s2=GET_ANS(c[i].y);
if(s1>s2) return ask(_id[i]);
}
return Lat=x,s1;
}
int main()
{
n=read(),m=read();
for(int i=1,x,y;i<n;++i)
x=read(),y=read(),add(x,y,read());
dfs_(),dfs__(),Sum=f[rt]=n,GET_ROOT(),dfs();
while(F[Lat]) Lat=F[Lat];
for(int i=1,x,d;i<=m;++i)
x=read(),d=read(),change(x,d),printf("%lld\n",ask());
return 0;
}
