【x义x讲坛】非常养生的点分治

· · 个人记录

\color{green}\Large\texttt{『菜鸡的blog』}

UPD9.14：规范了“祖先”“父亲”“儿子”“后代”等用语。祖先指父亲，父亲的父亲，父亲的父亲的父亲等等。后代则指儿子，儿子的儿子，儿子的儿子的儿子等等。

UPD10.25：继续了动态点分治的学习。

点分治基础

问题引入：P3806 【模板】点分治1

显然每次询问都枚举点对然后计算距离的话，是不可能过的。我们直接切入正题来讲点分治。

我们给树选一个根，那么树上的路径显然可以分成两类：第一类是经过根的，第二类是不经过根的。对于不经过根的路径，它一定是整条路径都在根节点的某一个儿子树内。于是，我们可以把第二类路径的求解归结于对每一棵儿子树的所有路径的求解，对于第一类路径，我们等下再讲。

其实这个就是点分治的核心思想：把一棵树分成一些子树分别求解。如图：

然而上面这个方法会被树是一条链，根是链的一端的数据给卡成N^2，非常难受。我们注意到这是一个分治，我们会被这种数据卡掉就是因为我们没有有效削减子问题的规模，那么我们怎么有效削减子问题的规模呢？

你可能已经往根节点的选取上面想了。没错，我们下面引入一个优秀的根节点：树的重心的概念。

我们知道在树中去掉一个节点会剩下一个森林，我们如果要有效削减子问题的规模，就要使这个森林里任意一棵树的大小尽量小。我们规定，树的重心就是使得这些树的大小的最大值最小的节点。

有这样一个结论：

以重心为根的大小为N的树，任意一棵子树大小不超过N/2。

还是比较显然的。如果有一棵子树大小超过了N/2，那么这棵子树的根当重心一定比当前重心更好，具体不讲了。

那么我们得到一个流程：

是的，我们在子树里也要重新找重心。反正是关于路径的问题，瞎捷豹换根没有关系。

每次分治规模便至少减半，那么可以证明这样搞下去复杂度为N\log N。

点分治大体思路讲完了，我们来看一下例题。

P3806 【模板】点分治1

对啊，我们好像还没讲这题到底该怎么处理第一类路径呢……

显然第一类路径(u,v)的长度就是dis[u]+dis[v]（dis[x]=x到根即重心的距离），那么我们可以先把所有子节点的dis排个序，然后满足dis[v]=K-dis[u]的v一定全靠在一块了，可以二分出左边界和右边界然后贡献等于R-L+1。（其实用两个指针一个从头向尾挪一个从尾向头挪也可以，但是前面有一个快排限制了复杂度，所以这个操作是不能减小复杂度的）

个头啊……这样会出现不合法的、属于第二类的路径（即u,v在同一子树中），或者说，它们在点分树上的 lca 并不是当前这个根。

但是我们可以通过一个容斥解决。比如i的儿子为j_1,j_2,...,j_k，我们要统计i中距离为K的点对。实际应该返回刚才统计的（统计错了的）第一类路径+所有的j中距离为K的点对-（统计错了的）所有的j中长度小于等于K-2*val(i,j) 的第一类路径。

不过其实可以通过大力染色的方式绕过容斥。

下面是标程：

#include <bits/stdc++.h>
using namespace std;

int N,M;

int lnk[10005];
int pre[20010],tgt[20010],val[20010],cnt;
void add_E(int u,int v,int c){
    pre[++cnt]=lnk[u],tgt[cnt]=v,val[cnt]=c,lnk[u]=cnt;
}

bool used[10005];

int rt;
int f[10005],s[10005];
void find_rt(int x,int fa,int S){
    f[x]=0,s[x]=1;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]]){
        find_rt(tgt[e],x,S);
        f[x]=max(f[x],s[tgt[e]]);
        s[x]+=s[tgt[e]];
    }
    f[x]=max(f[x],S-s[x]);
    if(f[x]<f[rt]) rt=x;
}

int tot,dis[10005];
void Get_dis(int x,int fa,int D){
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&(!used[tgt[e]])){
        dis[++tot]=val[e]+D;
        Get_dis(tgt[e],x,val[e]+D);
    }
}

int bis_r(int l,int k){
    int r=tot,mid,ans=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(dis[mid]<k) l=mid+1;
        else ans=mid,r=mid-1;
    }
    return ans;
}
int bis_l(int l,int k){
    int r=tot,mid,ans=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(dis[mid]<=k) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int Get_ANS(int x,int K,int D){
    dis[tot=1]=D;
    Get_dis(x,0,D);
    sort(dis+1,dis+tot+1);
    int l=1,ans=0;
    while(l<tot&&dis[l]+dis[tot]<K) l++;
    while(l<tot&&2*dis[l]<=K){
        int L=bis_r(l+1,K-dis[l]),R=bis_l(l+1,K-dis[l]);
        if(R>=L) ans+=R-L+1;
        l++;
    }
    return ans;
}

int ANS;
void DFZ(int x,int K){
    used[x]=1;ANS+=Get_ANS(x,K,0);
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]){
        ANS-=Get_ANS(tgt[e],K,val[e]);
        rt=0;f[0]=0x3f3f3f3f;
        find_rt(tgt[e],x,s[tgt[e]]);
        DFZ(rt,K);
    }
}

int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<N;i++){
        int u,v,c;scanf("%d%d%d",&u,&v,&c);
        add_E(u,v,c);add_E(v,u,c);
    }
    while(M--){
        int k;scanf("%d",&k);
        memset(used,0,sizeof(used));
        ANS=0;
        rt=0;f[0]=0x3f3f3f3f;
        find_rt(1,0,N);
        DFZ(rt,k);
        if(ANS) printf("AYE\n");
        else printf("NAY\n");
    }

    return 0;
}

P4178 Tree

另一道模板题。

P4149 [IOI2011]Race

和前两题不太一样的地方在于，点权范围变小了所以我们直接用桶就可以了我们这次还需要记录从祖先到一个点经过几条边。又因为现在是取最小值没法容斥，所以实际操作中，我们使用一个桶，记录从当前的根到dis为i的节点至少要过几条边。

这次排除不合法路径的方式是，等到该儿子树统计完之后才把该子树插入桶。

还有一点，桶不能直接memset清空，否则复杂度原地爆炸。我们要第三次搜进这个子树，对每个节点，把它的dis对应经过的边数在桶中设为inf。

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int maxN=200005;

int N,K;
int lnk[maxN];
int pre[maxN<<1],tgt[maxN<<1],val[maxN<<1],cnt;
void add_E(int u,int v,int c){
    pre[++cnt]=lnk[u],tgt[cnt]=v,val[cnt]=c,lnk[u]=cnt;
}

bool used[maxN];
int ANS;

int rt;
int f[maxN],s[maxN];
void Get_rt(int x,int fa,int S){
    f[x]=0;s[x]=1;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]]){
        Get_rt(tgt[e],x,S);
        f[x]=max(f[x],s[tgt[e]]);
        s[x]+=s[tgt[e]];
    }
    f[x]=max(f[x],S-s[x]);
    if(f[x]<f[rt]) rt=x;
}

int ans;
int bok[1000005];
void Get_dis(int x,int fa,int D,int d,int K){
    if(D>K) return;
    ans=min(ans,bok[K-D]+d);
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Get_dis(tgt[e],x,D+val[e],d+1,K);
}
void Ins_dis(int x,int fa,int D,int d){
    if(D>K) return;
    bok[D]=min(bok[D],d);
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Ins_dis(tgt[e],x,D+val[e],d+1);
}
void Emp_dis(int x,int fa,int D,int d){
    if(D>K) return;
    bok[D]=0x3f3f3f3f;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Emp_dis(tgt[e],x,D+val[e],d+1);
}

int Get_ans(int x,int K){
    ans=0x3f3f3f3f;
    bok[0]=0;
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]){
        Get_dis(tgt[e],x,val[e],1,K);
        Ins_dis(tgt[e],x,val[e],1);
    }
    Emp_dis(x,0,0,0);
    return ans;
}

void DFZ(int x,int K){
    used[x]=1;
    ANS=min(ANS,Get_ans(x,K));
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]){
        rt=0;f[0]=0x3f3f3f3f;
        Get_rt(tgt[e],x,s[tgt[e]]);
        DFZ(rt,K);
    }
}

int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<N;i++){
        int u,v,c;scanf("%d%d%d",&u,&v,&c);
        u++;v++;
        add_E(u,v,c);add_E(v,u,c);
    }
    rt=0;f[0]=0x3f3f3f3f;
    memset(bok,63,sizeof(bok));
    Get_rt(1,0,N);
    ANS=0x3f3f3f3f;
    DFZ(rt,K);
    if(ANS!=0x3f3f3f3f) printf("%d\n",ANS);
    else printf("-1\n");

    return 0;
}

P2664 树上游戏

摘自某题解：

？？？神仙吧

显然此题我只会O(N^3)做法。

自闭了，等再修炼几年再回来写这题博客……

P4886 快递员

点分治好题！代码很板子但又很有意思。

先定住一个重心为根，假装它就是我们要的那个运货中心了，然后我们可以很轻松地找出（当前）所有订单里长度最大的那几个。然后我们开始讨论。

如图，染红的两个点是其中一个长度最大的订单。

如果我们希望一个更优秀的答案，那么我们像方案1一样，向红链的两端移肯定不行，链长根本不会改变；像方案2一样，向其他子树移更不行，只会使得答案更大。

那么排除这种情况，现在（有机会使答案更小）的方案只可能是任意一个订单的两个节点都在同一子树内。

然而：

如果往红链走，绿色订单的长度就会增加；反之亦然。

于是现在只剩下了一种情况：仅有数个两端点都在同一子树内的最大订单。

那么这时，我们往这棵子树里走是有希望的。

注意是有希望而不是一定更好！反例如下：

显然绿订单是唯一的最大订单，长度为2000，但是当我们把根节点向绿色订单的方向移之后，红订单变为了最大订单，长度为2003。

于是代码也就不难写了。在淀粉质题目里简直是一股清流……

#include <bits/stdc++.h>
using namespace std;

int N,M;
int lnk[100005];
int pre[200005],tgt[200005],val[200005],cnt;
void add_E(int u,int v,int c){
    pre[++cnt]=lnk[u],tgt[cnt]=v,val[cnt]=c,lnk[u]=cnt;
}
int u[100005],v[100005];

bool used[100005];

int f[100005],s[100005];
int rt;
void Get_rt(int x,int fa,int S){
    f[x]=0;s[x]=1;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Get_rt(tgt[e],x,S),s[x]+=s[tgt[e]],f[x]=max(f[x],s[tgt[e]]);
    f[x]=max(f[x],S-s[x]);
    if(f[x]<f[rt]) rt=x;
}
int dep[100005],clr[100005];
void Get_dep(int x,int fa){
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa)
        dep[tgt[e]]=dep[x]+val[e],clr[tgt[e]]=clr[x],Get_dep(tgt[e],x);
}

int ANS=0x3f3f3f3f;
int stk[100005],len;
void DFZ(int x){
//  cout<<"DFZ"<<x<<endl;
    if(used[x]) return;
    clr[x]=x;used[x]=1;dep[x]=0;
    for(int e=lnk[x];e;e=pre[e])
        clr[tgt[e]]=tgt[e],dep[tgt[e]]=val[e],Get_dep(tgt[e],x);
    int ans=0;len=0;
    for(int i=1;i<=M;i++){
        if(dep[u[i]]+dep[v[i]]>ans) len=0,ans=dep[u[i]]+dep[v[i]];
        if(dep[u[i]]+dep[v[i]]==ans) stk[++len]=i;
    }
    ANS=min(ANS,ans);
    int lstclr=0;
    for(int k=1;k<=len;k++){
        int i=stk[k];
        if(clr[u[i]]!=clr[v[i]]) return;
        if(!lstclr) lstclr=clr[u[i]];
        if(clr[u[i]]!=lstclr) return;
    }
    rt=0;
    Get_rt(lstclr,x,s[lstclr]);
    DFZ(rt);
}

int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<N;i++){
        int tu,tv,tc;scanf("%d%d%d",&tu,&tv,&tc);
        add_E(tu,tv,tc);add_E(tv,tu,tc);
    }
    for(int i=1;i<=M;i++)
        scanf("%d%d",&u[i],&v[i]);
    f[0]=0x3f3f3f3f;rt=0;
    Get_rt(1,0,N);DFZ(rt);
    printf("%d\n",ANS);

    return 0;
}

P4183 [USACO18JAN]Cow at Large P

去年10月做了P4186，此题的超级弱化版（只有一个根），结果……不信抬头看，毒瘤饶过谁啊……

显然，如果一个节点到某个叶子节点的距离小于等于根到这个节点的距离，那么农民就可以比Bessie更早或是同时到达i，这样，花一个代价就把i的子树守住了。（下面称：存在一个农民可以不比Bessie晚地到达的节点“有贡献”。）

于是我们发现了一些性质。

我们现在比较难受的原因主要是：如果一个节点有贡献，那么我们拿一个代价（一个农民）去守它，那么它的整个子树都不需要花代价了。

根据刚才发现的性质二，一个节点有贡献，它的整个子树都有贡献。我们能不能有什么骚操作把整个子树的贡献视为1呢？

下面介绍一个小结论：

\sum_{x\in V}d[x]=2\left|V\right|-1

该结论显然。我们把它变形一下：

\sum_{x\in V}(2-d[x])=1

！！！

这个就是我们想要的，能把整个子树的贡献抵消成1的东西！！！

最后也就是求这样一个柿子：

ans[rt]=\sum_{x=1}^N(2-d[x])\big[\ dis(rt,x)\ge k[x]\ \big]

（\big[x\big]的意思是：x为真则返回1，否则返回0）

于是成了淀粉质板子题。

（不好意思其实我没看出来这是淀粉质板子题）

对于当前重心x，假设我们已经求出了每个节点到它的dis，如果有u，v分属两个子树，设rt=u，那么v就在dis[u]+dis[v]\ge k[v]的时候有贡献。

也就是在dis[u]\ge k[v]-dis[v]的时候对u有贡献2-d[v]。对于每个u我们都可以用树状数组快速统计。

当时在写代码的时候那几个查询/修改的顺序其实是瞎调的

#include <bits/stdc++.h>
using namespace std;

int N;
int lnk[70005],deg[70005];
int pre[140005],tgt[140005],cnt;
void add_E(int u,int v){
    deg[u]++;
    pre[++cnt]=lnk[u],tgt[cnt]=v,lnk[u]=cnt;
}

int q[70005],h,t;
int k[70005];
void bfs(){
    for(int i=1;i<=N;i++)
        if(deg[i]==1) q[++t]=i;
        else k[i]=-1;
    while(h!=t){
        int u=q[++h];
        for(int e=lnk[u];e;e=pre[e])if(k[tgt[e]]==-1)
            k[tgt[e]]=k[u]+1,q[++t]=tgt[e];
    }
}

bool used[70005];
int rt,f[70005],s[70005];
void Get_rt(int x,int fa,int S){
    f[x]=0;s[x]=1;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Get_rt(tgt[e],x,S),s[x]+=s[tgt[e]],f[x]=max(f[x],s[tgt[e]]);
    f[x]=max(f[x],S-s[x]);
    if(f[x]<f[rt]) rt=x;
}

int C[140005];
void chn(int x,int k){for(int x1=x+N+1;x1<=2*N;x1+=x1&-x1) C[x1]+=k;}
int qst(int x){int ans=0;for(int x1=x+N+1;x1;x1-=x1&-x1) ans+=C[x1];return ans;}

int Ans[70005];
void Query(int x,int fa,int dis){
    Ans[x]+=qst(dis);
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Query(tgt[e],x,dis+1);
}
void Update(int x,int fa,int dis,bool flg){
    if(!flg) chn(k[x]-dis,2-deg[x]);else chn(k[x]-dis,deg[x]-2);
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Update(tgt[e],x,dis+1,flg);
}

int stk[70005],len;
void DFZ(int x){
    used[x]=1;len=0;

    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]])
        stk[++len]=tgt[e];

    for(int i=1;i<=len;i++)
        Query(stk[i],x,1),Update(stk[i],x,1,0);
    for(int i=1;i<=len;i++) Update(stk[i],x,1,1);

    chn(k[x],2-deg[x]);
    for(int i=len;i;i--)
        Query(stk[i],x,1),Update(stk[i],x,1,0);
    chn(k[x],deg[x]-2);
    Ans[x]+=qst(0);
    for(int i=len;i;i--) Update(stk[i],x,1,1);

    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]){
        rt=0;Get_rt(tgt[e],x,s[tgt[e]]);
        DFZ(rt);
    }
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<N;i++){
        int u,v;scanf("%d%d",&u,&v);
        add_E(u,v);add_E(v,u);
    }
    bfs();
    f[0]=0x3f3f3f3f;rt=0;
    Get_rt(1,0,N);DFZ(rt);
    for(int i=1;i<=N;i++) printf("%d\n",Ans[i]);

    return 0;
}

P5306 [COCI2019] Transport

算出每个节点走到当前根还剩多少油，和如果从当前根出发走到该节点一开始至少要多少油。然后双指针/二分。对于去除子树内不合法答案的问题，直接暴力搞掉即可。

请看代码。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int N,A[100005];
bool used[100005];

int lnk[100005];
int pre[200005],tgt[200005],val[200005],cnt;
void add_E(int u,int v,int c){
    pre[++cnt]=lnk[u],tgt[cnt]=v,val[cnt]=c,lnk[u]=cnt;
}

int f[100005],s[100005],rt;
void Get_rt(int x,int fa,int S){
    f[x]=0;s[x]=1;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Get_rt(tgt[e],x,S),f[x]=max(f[x],s[tgt[e]]),s[x]+=s[tgt[e]];
    f[x]=max(f[x],S-s[x]);
    if(f[x]<f[rt]) rt=x;
}

ll lis1[100005];int len1;
ll lis2[100005];int len2;
ll key1[100005],key2[100005];

//K1表示还剩多少,K2表示最少需要一开始就加多少 
void Get_key(int x,int fa,ll l_oil,ll K1,ll K2){
    if(K2==0) lis1[++len1]=l_oil;
    lis2[++len2]=-K1;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=fa&&!used[tgt[e]])
        Get_key(tgt[e],x,l_oil-val[e]+A[tgt[e]],min(K1,l_oil-val[e]-A[rt]),min((ll)0,K2-val[e]+A[tgt[e]])); 
}

ll ans;

void Get_ans(int x){
    used[x]=1;
    len1=len2=0;
    lis1[++len1]=A[x];
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]){
        int l1=len1+1,l2=len2+1;
        Get_key(tgt[e],x,A[x]+A[tgt[e]]-val[e],-val[e],min(0,A[tgt[e]]-val[e]));
        if(l1<=len1&&l2<=len2){
            sort(lis1+l1,lis1+len1+1),sort(lis2+l2,lis2+len2+1);
            int r=l2;
            for(int l=l1;l<=len1;l++){
                while(r<=len2&&lis1[l]>=lis2[r]) r++;
                    ans-=r-l2;
            }
        }
    }
    sort(lis1+1,lis1+len1+1),sort(lis2+1,lis2+len2+1);
    int r=1;
    for(int l=1;l<=len1;l++){
        while(r<=len2&&lis1[l]>=lis2[r])++r;
            ans+=r-1;
    }
    ans+=len1-1;
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]){
        rt=0;Get_rt(tgt[e],x,s[tgt[e]]);Get_ans(rt);
    }
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&A[i]);
    for(int i=1;i<N;i++){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        add_E(u,v,c);add_E(v,u,c);
    }
    f[0]=0x3f3f3f3f;rt=0;
    Get_rt(1,0,N);Get_ans(rt);
    printf("%lld",ans);
}

小结

点分治的想法一般还是简单（但不一定好想）的，但是代码极度恶心。求重心，Get_dis（或者别的什么东西）（甚至还可能有两个及以上），Get_ans里的双指针/树状数组或者其他鬼畜的东西，再加上一些杂七杂八的组件就凑成了一份代码。

这就让你自闭了？世界的残酷还在外头呢……

动态点分治

动态点分治，就是在原来点分治的基础上，从每一个重心向它的“次级重心”（即该重心管辖的子树的重心）连一条边。这样重新建了树（称为点分树）之后树高显然是\log N级别的，于是可以暴力地不断跳（点分树上的）father来干一些事情。

（不幸的是这些事情都非常毒瘤）

先来看一道比较小清新的题目。

SP2939 QTREE5 - Query on a tree V

为什么Qtree5比Qtree4简单这么多……算了不管了

首先建出点分树。然后不需要太多其他准备工作，只需要再给每一个节点一个（代表了其管辖的子树的情况的）堆，一开始都为空。

如果是加点，暴力（在点分树上）跳fa并在每一个祖先的堆里塞一个当前节点（到这个祖先的dis）。

如果是删点，那么改成删除就行了。

堆的删除具体看代码。

暴力跳fa，每次把答案更新为当前堆里的最小值+当前所查询节点的dis。非常容易证明这肯定是对的。

#include<bits/stdc++.h>
using namespace std;

int N,M;
int lnk[100005];
int pre[200005],tgt[200005],cnt;
void add_E(int u,int v){
    pre[++cnt]=lnk[u],tgt[cnt]=v,lnk[u]=cnt;
}

bool used[100005],clr[100005];
int s[100005],f[100005];
int rt;
void Get_rt(int x,int fa,int S){
    f[x]=0;s[x]=1;
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]&&tgt[e]!=fa)
        Get_rt(tgt[e],x,S),s[x]+=s[tgt[e]],f[x]=max(f[x],s[tgt[e]]);
    f[x]=max(f[x],S-s[x]);
    if(f[x]<f[rt]) rt=x;
}
int FA[100005];
int K[100005];
int dis[21][100005];
void Get_dis(int x,int fa,int k,int d){
    dis[k][x]=d;
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]&&tgt[e]!=fa)
        Get_dis(tgt[e],x,k,d+1);
}
void DFZ(int x,int k){
    used[x]=1;K[x]=k;
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]])
        Get_dis(tgt[e],x,k,1);
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]){
        rt=0;
        Get_rt(tgt[e],x,s[tgt[e]]);
        Get_rt(rt,x,s[tgt[e]]);
        FA[rt]=x;
        DFZ(rt,k+1);
    }
}

priority_queue<int,vector<int>,greater<int> > Q1[100005],Q2[100005];
void Update(int x){
    int fa=x,k=K[x];
    while(k){
//      printf("fa = %d,k = %d,dis = %d\n",fa,k,dis[k][x]);
        if(!clr[x]) Q1[fa].push(dis[k][x]);
        else Q2[fa].push(dis[k][x]);
        k--;fa=FA[fa];
    }
    clr[x]^=1;
}
int Query(int x){
    int fa=x,k=K[x],ans=0x3f3f3f3f;
    while(k){
//      printf("fa = %d,k = %d,dis = %d\n",fa,k,dis[k][x]);
        while(Q1[fa].size())
            if(Q2[fa].size()&&Q1[fa].top()==Q2[fa].top())
                Q1[fa].pop(),Q2[fa].pop();
            else{ans=min(ans,Q1[fa].top()+dis[k][x]);break;}
        k--;fa=FA[fa];
//      printf("ans = %d\n",ans);
    }
    if(ans==0x3f3f3f3f) return -1;
    return ans;
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<N;i++){
        int u,v;scanf("%d%d",&u,&v);
        add_E(u,v);add_E(v,u);
    }
    f[0]=0x3f3f3f3f;Get_rt(1,0,N);Get_rt(rt,0,N);
    DFZ(rt,1);
//  for(int i=1;i<=N;i++) printf("Fa = %d\n",FA[i]);

    scanf("%d",&M);
    while(M--){
        int opt,u;scanf("%d%d",&opt,&u);
        if(opt==1) printf("%d\n",Query(u));
        else Update(u);
    }
}

P2056 [ZJOI2007]捉迷藏和P4115 Qtree4和SP2666 QTREE4 - Query on a tree IV

三倍经验的黑题好评

此题和Qtree5挺像的，可能有类似的思路。

如何查询答案？我们要求路径分属两个子树，所以我们要查询每个儿子树中，“节点到当前根路径的最小值”的最小值和次小值（加起来就是最长路径），还要支持删除（染成黑点），所以这个对每个点都要用两个（支持删除的）堆实现：

然后还要查询（和删除）答案。于是再开单独一个记录所有子树最长路径的堆。

代码十分毒瘤，如下：

#include<bits/stdc++.h>
using namespace std;

const int maxN=100005;

int N,M;
int lnk[maxN];
int pre[maxN<<1],tgt[maxN<<1],val[maxN<<1],cnt;
void add_E(int u,int v,int c){
    pre[++cnt]=lnk[u],tgt[cnt]=v,val[cnt]=c,lnk[u]=cnt;
}

int Dep[maxN];
int FA[20][maxN],FAL[20][maxN];
void InitDis(int x,int f,int fe){
    Dep[x]=Dep[f]+1,FA[0][x]=f,FAL[0][x]=fe;
    for(int k=1;k<=19;k++)
        FA[k][x]=FA[k-1][FA[k-1][x]],
        FAL[k][x]=FAL[k-1][x]+FAL[k-1][FA[k-1][x]];
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=f)
        InitDis(tgt[e],x,val[e]);
}
int Dis(int u,int v){
    int ans=0;
    if(Dep[u]<Dep[v]) swap(u,v);
    for(int k=19;k>=0;k--)
        if(Dep[FA[k][u]]>=Dep[v]) ans+=FAL[k][u],u=FA[k][u];
    if(u==v) return ans;
    for(int k=19;k>=0;k--)
        if(FA[k][u]!=FA[k][v])
            ans+=FAL[k][u],u=FA[k][u],
            ans+=FAL[k][v],v=FA[k][v];
    ans+=FAL[0][u],u=FA[0][u],
    ans+=FAL[0][v],v=FA[0][v];
    return ans;
}

struct Priority_Queue{
    priority_queue<int> q1,q2;int l1,l2;
    void Push(int x){q1.push(x);l1++;}
    void Pop(int x){q2.push(x);l2++;}
    int Top(){while(l1&&l2&&q1.top()==q2.top()) q1.pop(),q2.pop(),l1--,l2--;if(l1) return q1.top();return -0x3f3f3f3f;}
    int TTop(){
        if(l1-l2<2) return 0;
        int ans1,ans2;
        ans1=Top();Pop(ans1);ans2=Top();Push(ans1);
        return max(ans1+ans2,0);
    }
}Q1[maxN],Q2[maxN],ANS;

int s[maxN],sf[maxN];
bool used[maxN];
void GetSiz(int x,int f){
    s[x]=1;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=f&&!used[tgt[e]])
        GetSiz(tgt[e],x),s[x]+=s[tgt[e]];
}
int rt;
void GetRt(int x,int f,int S){
    sf[x]=0;
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=f&&!used[tgt[e]])
        GetRt(tgt[e],x,S),sf[x]=max(sf[x],s[tgt[e]]);
    sf[x]=max(sf[x],S-s[x]);
    if(sf[x]<sf[rt]) rt=x;
}
void GetDep(int x,int f,int nrt,int prt){
    Q1[nrt].Push(Dis(x,prt));
    for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=f&&!used[tgt[e]])
        GetDep(tgt[e],x,nrt,prt);
}

int Fa[maxN];
void DFZ(int x,int f){
    used[x]=1;
    GetDep(x,0,x,f);
    Q2[x].Push(0);
    for(int e=lnk[x];e;e=pre[e])if(!used[tgt[e]]){
        rt=0;
        GetRt(tgt[e],x,s[tgt[e]]);
        int Son=rt;
        GetSiz(Son,x);
        Fa[Son]=x;
        DFZ(Son,x);
        Q2[x].Push(Q1[Son].Top());
    }
    ANS.Push(Q2[x].TTop());
}

void ADD(int x){
    int bq1,aq1,bq2,aq2;
    bq2=Q2[x].TTop();Q2[x].Push(0);aq2=Q2[x].TTop();
    if(bq2!=aq2) ANS.Pop(bq2),ANS.Push(aq2);
    for(int x1=x;Fa[x1];x1=Fa[x1]){
        bq1=Q1[x1].Top();Q1[x1].Push(Dis(Fa[x1],x));aq1=Q1[x1].Top();
        if(bq1!=aq1){
            bq2=Q2[Fa[x1]].TTop();
            if(bq1!=-0x3f3f3f3f) Q2[Fa[x1]].Pop(bq1);
            if(aq1!=-0x3f3f3f3f) Q2[Fa[x1]].Push(aq1);
            aq2=Q2[Fa[x1]].TTop();
            if(bq2!=aq2) ANS.Pop(bq2),ANS.Push(aq2);
        }
    }
}
void DEL(int x){
    int bq1,aq1,bq2,aq2;
    bq2=Q2[x].TTop();Q2[x].Pop(0);aq2=Q2[x].TTop();
    if(bq2!=aq2) ANS.Pop(bq2),ANS.Push(aq2);
    for(int x1=x;Fa[x1];x1=Fa[x1]){
        bq1=Q1[x1].Top();Q1[x1].Pop(Dis(Fa[x1],x));aq1=Q1[x1].Top();
        if(bq1!=aq1){
            bq2=Q2[Fa[x1]].TTop();
            if(bq1!=-0x3f3f3f3f) Q2[Fa[x1]].Pop(bq1);
            if(aq1!=-0x3f3f3f3f) Q2[Fa[x1]].Push(aq1);
            aq2=Q2[Fa[x1]].TTop();
            if(bq2!=aq2) ANS.Pop(bq2),ANS.Push(aq2);
        }
    }
}

bool clr[maxN];
int tot;

char str[5];
int main(){
    sf[0]=0x3f3f3f3f;
    scanf("%d",&N);
    for(int i=1;i<N;i++){
        int u,v,c;scanf("%d%d%d",&u,&v,&c);
        add_E(u,v,c);add_E(v,u,c);
    }

    InitDis(1,0,0);

    rt=0;
    GetSiz(1,0);
    GetRt(1,0,s[1]);
    GetSiz(rt,0);
    DFZ(rt,1);
    scanf("%d",&M);
    tot=N;
    while(M--){
        scanf("%s",str);
        if(str[0]=='C'){
            int pos;scanf("%d",&pos);
            if(clr[pos]) tot++,clr[pos]=0,ADD(pos);
            else tot--,clr[pos]=1,DEL(pos);
        }
        else
            if(tot) printf("%d\n",ANS.Top());
            else printf("They have disappeared.\n");
    }
}

因为人丑常数大卡不过SPOJ上的Qtree4……

P3345 [ZJOI2015]幻想乡战略游戏

啊♂？幻♂想♂乡？

众所周知动态点分治的题目时限都非常鬼畜，这题又是路径问题而且树剖/LCT貌似解决不了，那大概就是动态点分治了。

（咕咕中）