[TOI 2015 4模] P Game

題目：

給定一棵$n$個點的樹，每條邊都有個長度，然後有$Q$次操作/詢問，每次可以佔領一個點，或是詢問某個點到所有已被佔領的點的距離總和。$n,Q\leq 10^5$。

作法：

這題有兩種作法，第一種作法是用平方分割，因為如果是一次佔領完再全部詢問，那麼我們可以用 DFS $O(n)$ 求出每個點的答案，再$O(1)$回答詢問，詳細作法就不提了。而另外一種作法則是：把所有被佔領的點紀錄下來，每次詢問就直接去詢問給定點和所有被佔領點的距離總和，這樣一次的複雜度會是$O(被佔領點個數\cdot logn)$。於是我們考慮把兩種作法合併，當一個一個佔領點時，如果此時佔領的點還沒有那麼多，則直接用求距離再加起來的作法硬算，而當要硬算的點個數達到某個值（假設為$K$）時，就 DFS 一次把所有點的答案都更新好，這樣在詢問時我們就有了詢問的點到前$K$個被佔領點的距離總和了，剩下的部份就硬算即可。這樣可以得到單次詢問的複雜度為$O(Klogn)$，佔領一個點時因為我們不會 DFS 超過$\frac{Q}{K}$次，因此複雜度會是$O(\frac{Q}{K}n)$。由這兩式就可以知道取$K$讓$QKlogn=\frac{Q}{K}n$會是最好的，移項得$K=\sqrt{\frac{n}{logn}}$，總複雜度為$O(Q\sqrt{nlogn})$。但考試時不知道為什麼怎麼取$K$都TLE，後來乾脆取個$100$還$200$就莫名其妙的過了。

事實上可以做到單次詢問$O(logn)$，用的東西叫重心剖分，他的概念是先對原本的樹取重心，把樹分成很多個子樹，再對這些子樹遞迴下去取重心，並且將原樹的重心和其子樹們的重心連起來，這樣我們就得到了一棵重心樹（重心樹上的邊不一定在原樹上出現，但每個點都出現了），不難證明其深度會是$O(logn)$的（之後稱重心樹上的一個子樹為重心子樹）。因此當詢問一個點$x$的答案時，可以直接沿著重心樹往上走（因此要紀錄好每個點在重心子樹上的父親是誰），並在走的過程維護當前答案等於「$x$到當前重心子樹裡所有已被佔領點的距離總和」，這樣一路走到根就獲得答案了。接下來我們要知道如何維護好答案，記當前重心子樹為$T$，他的根$P$，還有如果只看原樹中這棵重心子樹裡的所有點的話，把$P$拔掉會讓他分成許多（原樹中的）子樹，稱其為$T_1,...,T_r$，並且不妨設$x$落在$T_1$裡面。那麼此時所求答案就必須要增加「$x$到所有$T_2,...,T_r$中被佔領點的距離」。這可以拆成兩部份，因為$x$走到這些點都必須經過$P$，因此如果假設在$T_2,...,T_r$中被佔領的點共有$t$個，那麼就可以把所求改成$t\cdot dist(P,x)+P$到$T_2,...,T_r$中被佔領點的距離總和（其中$dist$ 代表兩點在原樹中的距離）。對於前者，我們可以在預處理時，對於每個重心子樹，把他的根到所有他在重心子樹中的點的（在原樹中的）距離都存起來，這樣就能知道$dist(P,x)$了。再來則是要知道$t$，而這可以用「$T$中的被佔領點數扣掉$T_1$中的被佔領點數」得到，因此只要在多佔領一個點時沿重心樹走上去，維護好每個重心子樹中的被佔領點數就好了。最後則是要知道$P$到$T_2,...,T_r$中所有被佔領點的距離總和，這可以拆成「$P$到$T$中所有被佔領點的距離總和」扣掉「$P$到$T_1$中所有被佔領點的距離總和」，因此也只要在新佔領點時維護好這兩個值就可以了，都是利用到已算好的「重心到其子樹中某個點的距離」。

實作有很多寫法，但大部份都很麻煩，畢竟我們要存$P$的每個子樹的一些資訊，還有$P$到其子樹內每個點的距離。一個比較簡潔的記法是，首先我們先對每個點紀錄他是落在重心樹深度多少的地方，那麼如果我們想要紀錄某個重心$P$到某個點$x$的距離，就把這個值存在$dis[dep[P]][x]$裡面就可以了，其中$dep$代表這個點在重心樹上的深度，不難發現這個存法不會讓兩個要存的東西碰撞。再來也蠻麻煩的則是要存：對於每個重心$P$，紀錄他的每個子樹中被佔領的點離他的距離總和，而這也可以只用一個陣列來存，假設$P$在重心樹上落在$T_1$的子節點為$Q$，那麼就直接把$P$到$T_1$中被佔領點的距離總和存到$Q$的位子就可以了，也不難發現這樣不會碰撞。另外剩下的「$P$這個重心子樹中所有被佔領點到他的距離總和和有幾個被佔領點」當然只要存在$P$的位子就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10,LOG=20 ;
 
struct P{int to,dis;};
vector<P> v[maxn] ;
int size[maxn] ;
 
LL dis[LOG][maxn] ;
int fa[maxn],vis[maxn] ;
int gfa[maxn],dep[maxn] ;
LL sum[maxn],sum2[maxn] ;
int num[maxn] ;
 
int get_cent(int st)
{
    static int qu[maxn] ;
    int sz=0 ; qu[sz++]=st ; fa[st]=-1 ;
    for(int i=0;i<sz;i++) for(auto j : v[qu[i]])
        if(j.to!=fa[qu[i]] && dep[j.to]==-1)
            fa[j.to]=qu[i] , qu[sz++]=j.to ;
 
    int ret=-1 , M=maxn ;
    for(int i=sz-1;i>=0;i--)
    {
        int x=qu[i],ma=0 ; size[x]=1 ;
        for(auto j : v[x]) if(j.to!=fa[x] && dep[j.to]==-1)
            size[x]+=size[j.to] , ma=max(ma,size[j.to]) ;
        ma=max(ma,sz-size[x]) ;
        if(ma<M) M=ma , ret=x ;
    }
    return ret ;
}
 
void dfs(int x,int f,LL di,int Gdep)
{
    dis[Gdep][x]=di ;
    for(auto i : v[x]) if(i.to!=f && dep[i.to]==-1)
        dfs(i.to,x,di+i.dis,Gdep) ;
}
 
void cent_decomp(int x,int Gfa,int Gdep)
{
    x=get_cent(x) ; gfa[x]=Gfa ;
    dep[x]=Gdep ;
    dfs(x,-1,0,Gdep) ;
    for(auto i : v[x]) if(dep[i.to]==-1)
        cent_decomp(i.to,x,Gdep+1) ;
}
 
void modify(int x,int cent,int son,int Gdep)
{
    if(cent==-1) return ;
    num[cent]++ ;
    if(son==-1){modify(x,gfa[cent],cent,Gdep-1) ; return ;}
    sum[cent]+=dis[Gdep][x] ;
    sum2[son]+=dis[Gdep][x] ;
    modify(x,gfa[cent],cent,Gdep-1) ;
}
 
LL query(int x,int cent,int son,int Gdep)
{
    if(cent==-1) return 0 ;
    LL ret= son==-1 ? sum[cent] :
        (num[cent]-num[son])*dis[Gdep][x]+sum[cent]-sum2[son] ;
    return ret+query(x,gfa[cent],cent,Gdep-1) ;
}
 
bool occ[maxn] ;
main()
{
    int n,Q ; scanf("%d%d",&n,&Q) ;
    for(int i=1;i<n;i++)
    {
        int x,y,di ; scanf("%d%d%d",&x,&y,&di) ;
        v[x].push_back((P){y,di}) ;
        v[y].push_back((P){x,di}) ;
    }
    memset(dep,-1,sizeof(dep)) ;
    cent_decomp(0,-1,0) ;
    while(Q--)
    {
        int t,x ; scanf("%d%d",&t,&x) ;
        if(t==1 && !occ[x]) occ[x]=1 , modify(x,x,-1,dep[x]) ;
        else if(t==2) printf("%lld\n",query(x,x,-1,dep[x])) ;
    }
}