洛谷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;
}