洛谷P3345 [ZJOI2015]幻想乡战略游戏（动态点分治，树的重心，二分查找，Tarjan-LCA，树上差分）

洛谷题目传送门

动态点分治小白，光是因为思路不清晰就耗费了不知道多少时间去gang这题，所以还是来理理思路吧。

一个树\(T\)里面\(\sum\limits_{v\in T} D_vdist(u,v)\)取到最小值的\(u\)我们可以称作带权重心。类似重心各种性质的证明过程，我们不难证出这样的点顶多只有两个。

如果\(e\)都是正数的话比较好做。类比重心性质，新带权重心一定在原带权重心和修改点之间的路径上，可以直接像首都（蒟蒻题解）那样用LCT维护以带权重心为根的树，修改时提出链二分查找出新带权重心即可。

可是\(e\)会是负数啊！这时候，新带权重心一定会有远离修改点的趋势。但是子树太多了，我们根本不能快速知道往哪里移。我们只能暴力判断，如果当前决策点是\(x\)，\(y\)与\(x\)有边相连，那么假如把补给站移过去，显然答案会减去\(y\)一侧子树的\(w×\sum\limits_{v\in Y} D_v\)（\(w\)为当前边权），加上\(x\)一侧子树的\(w×\sum\limits_{v\in X} D_v\)。那么当\(\sum\limits_{v\in Y} D_v\geq\sum\limits_{v\in X} D_v\)也就是\(2\sum\limits_{v\in Y} D_v\geq\sum\limits_{v\in T} D_v\)时我们当然可以更改决策点，然后继续寻找更优的点，直到找不到为止。只可惜这样是\(O(n^2)\)的。

怎么快速找呢？我们可以想到动态点分治，点分树的高度是\(\log\)级别的，把它建好后，维护每个以\(u\)为根的点分子树的\(D\)之和\(s_u\)。根据上式判断，如果当前点的某一个有边相邻的点更优，我们直接把决策点改成该点所在的点分子树的根节点！由于每个点度数很小，我们甚至可以暴力for一遍判断。这也是像首都一样二分查找重心。

但是，具体实现起来又有不少问题。

首先，点分树保证了高度，却保证不了信息的完整性，每个节点只能维护该节点所在点分子树的信息。而上面那个式子需要维护原树的子树\(\sum D\)。试想一下当我们在点分树里从根向下跳了\(k\)层，那么当前的子树还会通过边连接上\(O(k)\)个外部子树。如果for每一条边的时候都要判断每一个外部子树在边的哪一侧，岂不是很费劲？

聪明的做法，可以理解为缩点，是在每次找到更优点之后，跳向点分子树\(v\)之前，把更优点的\(D\)临时加上\(s_u-s_v\)即外部子树的\(\sum D\)。当然，注意区分点分树和原树，更优点并不一定是当前点的子节点，所以更优点的点分树上的祖先的\(s\)也要更新。用递归实现，等到找出了带权重心，回溯了之后，再把它还原。稍稍脑补一下，是不是很轻松地消除了外部子树的影响？

其次，找出了重心，我们还要统计答案。仔细想想，这个答案实在不方便也没必要丢到别的数据结构（线段树，LCT什么的）动态维护了。把点分树建出来了，还不好好使用它？我们显然要维护每个以\(x\)为根点分子树中的\(\sum\limits_{v\in X} D_vdist(x,v)\)，记为\(tot_x\)。设统计\(x\)的答案，首先\(tot_x\)直接算进去了。但是如果加上\(x\)祖先的\(tot\)，就会有多余的，多余出\(x\)所在点分子树的贡献。这时候来一波树上差分，再记\(tof_x\)表示\(\sum\limits_{v\in X} D_vdist(fa_x,v)\)（\(fa_x\)为\(x\)点分树上的父亲），每加上\(tot_{fa_x}\)就减掉\(tof_x\)就好啦。

思路至此，点分树里的三个变量怎么维护也不是大问题了。当\(D_x\)加上\(e\)的时候，更新点分树上\(x\)及其祖先，设当前修改\(y\)，那么\(s_y\)加上\(e\)、\(tot_{fa_y}\)和\(tof_y\)都加上\(e×dist(x,{fa_y})\)就是显然的了。那么我们还要预处理出每个点到点分树上每个祖先的距离，这个可以离线，为什么没人写Tarjan求LCA呢？（话说蒟蒻也是第一次写）把询问丢进去，以\(1\)为根求每个点的带权深度\(dep\)，处理出LCA之后直接差分，\(dist(x,y)=dep_x+dep_y-2dep_{LCA}\)，这个大家都会吧。

思路实在不清晰就看看代码吧。话说动态点分治的代码都短不了吧。。。。。。不过Tarjan写起来方便不少，蒟蒻没过分压行也只有90多行。

#include<cstdio>
#include<cstring>
#define LL long long
#define RG register
#define R RG int
#define G c=getchar()
const int N=1e5+9,M=2e5+9,L=2e6;
namespace E{int he[N],ne[M],to[M];}//原树
namespace T{int he[N],ne[N],to[N];}//点分树
namespace Q{int he[L],ne[L<<1],to[L<<1];}//LCA询问
using namespace E;//封了namespace确实清楚多了
int n,p,rt,w[M],s[N],mx[N],h[N],dep[N],fa[N],top[N],dis[N][20],*at[L<<1];
LL tot[N],tof[N];//该开longlong的别忘记
bool vis[N];
inline int in(){
RG char G;RG bool f=0;
while(c<'-')G;
if(c=='-')f=1,G;
R x=c&15;G;
while(c>'-')x*=10,x+=c&15,G;
return f?-x:x;
}
inline void max(R&x,R y){if(x<y)x=y;}
void getrt(R x){//建点分树求重心
vis[x]=1;s[x]=1;mx[x]=0;
for(R y,i=he[x];i;i=ne[i]){
if(vis[y=to[i]])continue;
getrt(y);
s[x]+=s[y];max(mx[x],s[y]);
}
max(mx[x],n-s[x]);
if(mx[rt]>mx[x])rt=x;
vis[x]=0;
}
int div(R x){//递归建树
getrt(x);vis[x=rt]=1;rt=0;
for(R t=n,y,i=he[x];i;i=ne[i]){
if(vis[y=to[i]])continue;
n=s[x]>s[y]?s[y]:t-s[x];
T::ne[++p]=T::he[x];T::he[x]=p;
fa[T::to[T::he[x]]=div(top[p]=y)]=x;
}//小心递归后p变了，写T::to[p]会出事
return x;
}
int geth(R x){return x==h[x]?x:h[x]=geth(h[x]);}//路径压缩
void tarjan(R x){//预处理dist
vis[x]=1;
for(R y,i=he[x];i;i=ne[i]){
if(vis[y=to[i]])continue;
dep[y]=dep[x]+w[i];
tarjan(y);h[y]=x;
}
for(R y,i=Q::he[x];i;i=Q::ne[i])
if(vis[y=Q::to[i]])
*at[i]=dep[x]+dep[y]-(dep[geth(y)]<<1);//差分
}
LL find(R x){
R i;
for(i=T::he[x];i&&s[T::to[i]]<<1<s[x];i=T::ne[i]);//找更优点
if(!i)return x;//找不到的话当前点就是最优点
R y,del=s[x]-s[T::to[i]];
for(y=top[i];y!=x;y=fa[y])s[y]+=del;//缩点
R ret=find(T::to[i]);
for(y=top[i];y!=x;y=fa[y])s[y]-=del;//还原
return ret;
}
int main(){
mx[0]=1e9;//记得给初值
R n=::n=in(),q=in(),x,y,v,i;
for(i=1;i<n;++i){
x=in();y=in();
ne[++p]=he[x];to[he[x]=p]=y;
ne[++p]=he[y];to[he[y]=p]=x;
w[p]=w[p-1]=in();
}
p=0;rt=div(1);p=0;
for(x=1;x<=n;++x)
for(i=0,y=fa[h[x]=x];y;y=fa[y],++i){
Q::ne[++p]=Q::he[x];Q::to[Q::he[x]=p]=y;
Q::ne[++p]=Q::he[y];Q::to[Q::he[y]=p]=x;
at[p]=at[p-1]=&dis[x][i];//搞个指针，Tarjan的时候直接把值放进去
}
memset(vis,0,n+1);memset(s,0,(n+1)<<2);//之前用过要清空
tarjan(1);
RG LL t;
while(q--){
x=y=in();s[rt]+=v=in();
for(i=0;y!=rt;++i)//维护
t=(LL)dis[x][i]*v,s[y]+=v,tof[y]+=t,tot[y=fa[y]]+=t;
t=tot[x=y=find(rt)];
for(i=0;y!=rt;++i)//算答案
t+=(LL)dis[x][i]*(s[fa[y]]-s[y])+tot[fa[y]]-tof[y],y=fa[y];
printf("%lld\n",t);
}
return 0;
}