[CF 526G] Spiders Evil Plan

作法：

我寫的作法跟這篇寫的一樣，這裡大概提一下實作的方法跟證明。
首先當然是找出重心，然後預處理出每個點往下走到葉子的最長距離，還有他應該要往哪個子節點走才可以走到最遠的葉子。這樣就可以用一個 priority_queue 來處理「一直把路徑拔掉」的操作了。具體來說，priority_queue 裡面放的是所有現在候選的鍊的深度最淺的點，還有這條鍊的長度，當我們把一條鍊從 priority_queue 裡面拿出來時，就沿著這條鍊走下去，並且對於走到的每一個點 $X$ ，假設他沿著鍊往下走的點為 $Y$ ，那麼就把 $X$ 除了 $Y$ 以外的所有子節點 $Z$ 都加入 priority_queue 中，並且可以知道 $Z$ 所代表的鍊長為 $d[ Z ] + dis[ X ] [ Z ]$ ，其中 $d$ 代表每個點往下走到葉子的最長距離， $dis$ 則是兩點之間的距離。而再處理詢問時，我們還要知道前 $2y$ 條鍊的總長度是多少，所以會需要一個前綴和陣列，還有一個點是落在第幾條鍊上。另外當詢問的 $x$ 沒有落在前 $2y$ 條鍊上時，會必須要沿著 $x$ 往上走，走到第一個落在前 $2y$ 條鍊上的點，而這個部份就可以用類似在找 LCA 的倍增法處理，所以要先預處理好每個點的 $2^k$ 級祖先是誰。

至於證明，當前 $2y$ 條鍊已經包含 $x$ 了的話是顯然的，以下只考慮不包含 $x$ 的情形。事實上對於一次的詢問，有一個貪心的算法是：以 $x$ 為根建出這棵樹，然後依次取 $2y$ 次葉節點，使得每次多取一個葉節點時可以讓總長增加的最多，這樣會是最好的選法。但是當我們所有選的鍊都是落在 $x$ 的同一個子節點 $y$ 底下時，這樣就會變成總共有 $2y + 1$ 個葉節點，不符合要求，因此必須把其中一條捨棄掉，加入一條 $x$ 往 $y$ 以外的子節點連過去並且連到最遠葉子的路徑。那麼回到現在這張以重心為根的圖，會得到以 $x$ 為根時貪心所選的 $2y$ 條鍊都會是往 $x$ 的祖先的方向（否則以重心為根的前 $2y$ 條鍊會選到 $x$），所以必須捨棄掉其中一條，並加上 $d[ x ]$ ，這就和上面的算法一致了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
struct P{int to,dis;};
vector<P> v[maxn] ;
 
int n,anc[18][maxn],dis[maxn] ;
void dfs(int x,int f,int d)
{
    anc[0][x]=f ; dis[x]=d ;
    for(auto i : v[x]) if(i.to!=f)
        dfs(i.to,x,d+i.dis) ;
}
 
int get_cent()
{
    dfs(1,1,0) ;
    int id,M=-1 ;
    for(int i=1;i<=n;i++) if(dis[i]>M) M=dis[id=i] ;
    dfs(id,id,0) ;
    int id2 ; M=-1 ;
    for(int i=1;i<=n;i++) if(dis[i]>M) M=dis[id2=i] ;
 
    int mi=M , cent ;
    for(int i=id2;i!=id;i=anc[0][i])
    {
        int val=max(dis[i],M-dis[i]) ;
        if(val<=mi) mi=val , cent=i ;
    }
    return cent ;
}
 
int mson[maxn],mdis[maxn] ;
void dfs2(int x,int f,int d)
{
    anc[0][x]=f ;
    for(int i=1;i<18;i++) anc[i][x]=anc[i-1][anc[i-1][x]] ;
    dis[x]=d ; mson[x]=-1 ; mdis[x]=0 ;
    for(auto i : v[x]) if(i.to!=f)
    {
        dfs2(i.to,x,d+i.dis) ;
        if(i.dis+mdis[i.to]>mdis[x])
            mdis[x]=i.dis+mdis[mson[x]=i.to] ;
    }
}
 
struct Q
{
    int id,val ;
    bool operator < (const Q &rhs) const
    {
        return val<rhs.val ;
    }
};
 
int chid[maxn],chcnt=0 ;
int len[maxn] ;
priority_queue<Q> pq ;
void build(int root)
{
    pq.push((Q){root,mdis[root]}) ;
    while(!pq.empty())
    {
        Q u=pq.top() ; pq.pop() ;
        len[++chcnt]=u.val ;
        for(int i=u.id;i!=-1;i=mson[i])
        {
            chid[i]=chcnt ;
            for(auto j : v[i]) if(j.to!=anc[0][i] && j.to!=mson[i])
                pq.push((Q){j.to,j.dis+mdis[j.to]}) ;
        }
    }
}
 
int lsum[maxn] ;
main()
{
    int Q ; scanf("%d%d",&n,&Q) ;
    for(int i=1;i<n;i++)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        v[x].push_back((P){y,dis}) ;
        v[y].push_back((P){x,dis}) ;
    }
 
    int root=get_cent() ;
    dfs2(root,root,0) ;
    build(root) ;
    for(int i=1;i<=chcnt;i++) lsum[i]=lsum[i-1]+len[i] ;
    for(int q=1,last=0;q<=Q;q++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        if(q>1) x=(x+last-1)%n+1 , y=(y+last-1)%n+1 ;
        if(2*y>=chcnt) printf("%d\n",last=lsum[chcnt]) ;
        else if(chid[x]<=2*y) printf("%d\n",last=lsum[2*y]) ;
        else
        {
            int x2=x ;
            for(int i=17;i>=0;i--) if(chid[anc[i][x2]]>2*y)
                x2=anc[i][x2] ;
            x2=anc[0][x2] ;
            int ans=lsum[2*y]+mdis[x]+(dis[x]-dis[x2]) ;
            printf("%d\n",last=ans-min(len[2*y],mdis[x2])) ;
        }
    }
}