VIII.[ZJOI2015]幻想乡战略游戏
题意：求一个树的带权重心，带修改。
现在首位的题解的方法太恶心了，这里介绍我自己的理解。
假设重心为\(x\)，我们有它的代价为：
其中\(val_i\)表示\(i\)节点的权值。
那如果将重心向\(x\)的某一个相邻节点\(y\)移动一格的话，
设\(\operatorname{len}(x,y)\)为连接\(x,y\)的边的权值，
则对于所有\(y\)一侧的节点，距离减少了\(\operatorname{len}(x,y)\)；对于所有\(x\)一侧的节点，这反而增加了\(\operatorname{len}(x,y)\)。
我们现在假设\(x\)为根。\(sum_i\)表示\(i\)节点的子树和，
则\(y\)一侧节点的贡献为\(sum_y\times\operatorname{len}(x,y)\)；
\(x\)一侧节点的贡献为\(-(sum_x-sum_y)\times\operatorname{len}(x,y)\)
两个东西加一起，整理整理，我们得到可以移动的充分必要条件为：
显然，对于每个\(x\)，这样的\(y\)唯一。
如果我们在原树上这么搞的话，显然会TLE（想想看如果是条链的话）。我们考虑到点分树上处理。
我们这次令\(sum_i\)表示点分树上子树和，而\(dssum_i\)表示：
如果\(i\)有父亲（即不是点分树的根），则为\(\sum\limits_{j\in subtree_i}val_j\times\operatorname{dis}(j,fa_i)\)。它的意义是到父亲的加权距离和。
否则，即它是点分树的根，则为\(\sum\limits_{j\in subtree_i}val_j\times\operatorname{dis}(j,i)\)。它的意义是到自己的加权距离和。
我们考虑当前在节点\(x\)。假设我们发现了一个子节点\(y\)符合\(2\times sum_y>sum_x\)，然后怎么办呢？
你可能会想着直接跳过去，但抱歉，点分树上的子树和不是真实的子树和，也就是说，这个\(sum_y\)不一定是真实的\(y\)侧节点贡献。
那怎么办呢？
我们考虑当\(x\)为点分树树根时，显然，这里的\(sum_y\)一定是真实的子树和。因此我们这里的\(y\)是可信的。
然后，这就是比较惊奇的地方了：
设一个\(z\)，它是\(y\)侧节点，同时直接与\(x\)相连。换句话说，\(z\)是原树上\(x\)在\(y\)侧的儿子。
我们把\(y\)子树外侧的所有东西，看作一个点，直接连到\(z\)上。
换句话说，当\(y\)为根的时候，它有许多儿子；但其中，\(x\)方向的那个是可以忽略的，因为\(y\)就是从\(x\)过来的，肯定不会再回去了；所以我们就把它连到\(z\)上，当作\(z\)的儿子。
可以参考LCT的虚儿子这一概念。
我们令一个\(imag\)数组表示虚儿子的\(dssum\)的和。然后，我们可以写出这样的求值部分：
ll ask(int x){
for(auto i:v[x]){//v is a vector<pair<int,int> >,which stores x's sons in the cdt and the 'z's they are corresponded to
int y=i.first,z=i.second;
if((sum[y]<<1)<=sum[x])continue;//judge if y is ok
ll cnt=val[x],out=imag[x];//cnt stands for the sum of val in 'x side', while out stands for all the nodes in 'x side', the sum of [their (distances to x) times (their val)]
for(auto u:v[x])if(u.first!=y)out+=dssum[u.first],cnt+=sum[u.first];//calculate cnt and out from the sons of x which are different from y
val[z]+=cnt;//the sum of val in the imagined subtree of z can be directly added onto val_z
ll olddssum=dssum[y];//store the original dssum_y for restore it later
fa[y]=0;//cut the edge between y and x, make y the root
dssum[y]=imag[y];//the values of the imagined sons
for(auto u:v[y])dssum[y]+=dssum[u.first];//the values of the real sons
imag[z]+=cnt*DIS(z,x)+out;//add (the value from x) to z
for(int u=z;u;u=fa[u])sum[u]+=cnt,dssum[u]+=cnt*(fa[u]?DIS(fa[u],x):DIS(u,x))+out;//the whole chain from x to z shall be updated
ll res=ask(y);
for(int u=z;u;u=fa[u])sum[u]-=cnt,dssum[u]-=cnt*(fa[u]?DIS(fa[u],x):DIS(u,x))+out;//restore the chain from z to z
imag[z]-=cnt*DIS(z,x)+out;//restore
fa[y]=x;//restore
dssum[y]=olddssum;//restore
val[z]-=cnt;//restore
return res;
}
return dssum[x];//if there's no proper son, then the answer is x itself
}
则这个东西的复杂度是\(O\Big(n\log n\times\max(\text{儿子数量},\log n)\Big)\)，因为找\(y\)时要统计所有儿子。但是题目最下面有一行：
非常神奇的是，对于所有数据，这棵树上的点的度数都不超过\(20\)。
点分树上儿子数量是不大于原树上儿子数量的，因此复杂度是正确的。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,dep[100100],mn[200100][20],in[100100],LG[200100],tot,fa[100100],fr[100100],admin;
namespace Tree{
int sz[100100],SZ,msz[100100],ROOT,head[100100],cnt;
struct node{
int to,next,val;
}edge[200100];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
bool vis[100100];
void getsz(int x,int fa){
sz[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next)if(!vis[edge[i].to]&&edge[i].to!=fa)getsz(edge[i].to,x),sz[x]+=sz[edge[i].to];
}
void getroot(int x,int fa){
sz[x]=1,msz[x]=0;
for(int i=head[x];i!=-1;i=edge[i].next)if(!vis[edge[i].to]&&edge[i].to!=fa)getroot(edge[i].to,x),sz[x]+=sz[edge[i].to],msz[x]=max(msz[x],sz[edge[i].to]);
msz[x]=max(msz[x],SZ-sz[x]);
if(msz[x]<msz[ROOT])ROOT=x;
}
void solve(int x){
getsz(x,0);
vis[x]=true;
for(int i=head[x];i!=-1;i=edge[i].next)if(!vis[edge[i].to])ROOT=0,SZ=sz[edge[i].to],getroot(edge[i].to,0),fa[ROOT]=x,fr[ROOT]=edge[i].to,solve(ROOT);
}
void getural(int x,int fa){
mn[++tot][0]=x,in[x]=tot;
for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dep[edge[i].to]=dep[x]+edge[i].val,getural(edge[i].to,x),mn[++tot][0]=x;
}
}
int MIN(int i,int j){
return dep[i]<dep[j]?i:j;
}
int LCA(int i,int j){
i=in[i],j=in[j];
if(i>j)swap(i,j);
int k=LG[j-i+1];
return MIN(mn[i][k],mn[j-(1<<k)+1][k]);
}
int DIS(int i,int j){
return dep[i]+dep[j]-dep[LCA(i,j)]*2;
}
namespace cdt{
vector<pair<int,int> >v[100100];
int val[100100];
ll sum[100100],dssum[100100],imag[100100];
void init(){
for(int i=1;i<=n;i++)if(fa[i])v[fa[i]].push_back(make_pair(i,fr[i]));
}
void modify(int x,int y){
val[x]+=y;
for(int u=x;u;u=fa[u]){
sum[u]+=y;
dssum[u]+=1ll*y*(fa[u]?DIS(fa[u],x):DIS(u,x));
}
}
ll ask(int x){
for(auto i:v[x]){
int y=i.first,z=i.second;
if((sum[y]<<1)<=sum[x])continue;//judge if y is ok
ll cnt=val[x],out=imag[x];//cnt stands for the sum of val in 'x side', while out stands for all the nodes in 'x side', the sum of [their (distances to x) times (their val)]
for(auto u:v[x])if(u.first!=y)out+=dssum[u.first],cnt+=sum[u.first];//calculate cnt and out from the sons of x which are different from y
val[z]+=cnt;//the sum of val in the imagined subtree of z can be directly added onto val_z
ll olddssum=dssum[y];//store the original dssum_y for restore it later
fa[y]=0;//cut the edge between y and x, make y the root
dssum[y]=imag[y];//the values of the imagined sons
for(auto u:v[y])dssum[y]+=dssum[u.first];//the values of the real sons
imag[z]+=cnt*DIS(z,x)+out;//add (the value from x) to z
for(int u=z;u;u=fa[u])sum[u]+=cnt,dssum[u]+=cnt*(fa[u]?DIS(fa[u],x):DIS(u,x))+out;//the whole chain from x to z shall be updated
ll res=ask(y);
for(int u=z;u;u=fa[u])sum[u]-=cnt,dssum[u]-=cnt*(fa[u]?DIS(fa[u],x):DIS(u,x))+out;//restore the chain from z to z
imag[z]-=cnt*DIS(z,x)+out;//restore
fa[y]=x;//restore
dssum[y]=olddssum;//restore
val[z]-=cnt;//restore
return res;
}
return dssum[x];//if there's no proper son, then the answer is x itself
}
}
int main(){
scanf("%d%d",&n,&m),memset(Tree::head,-1,sizeof(Tree::head));
for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),Tree::ae(x,y,z);
Tree::msz[0]=n+1,Tree::SZ=n,Tree::getroot(1,0),admin=Tree::ROOT,Tree::solve(Tree::ROOT);
Tree::getural(1,0);
for(int i=2;i<=tot;i++)LG[i]=LG[i>>1]+1;
for(int j=1;j<=LG[tot];j++)for(int i=1;i+(1<<j)-1<=tot;i++)mn[i][j]=MIN(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
// for(int i=1;i<=n;i++)if(fa[i])printf("%d %d\n",fa[i],i);
cdt::init();
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),cdt::modify(x,y),printf("%lld\n",cdt::ask(admin));
return 0;
}