根号大军占领 Qtree

· · 算法·理论

一、前言

昨天无意间看到了 QTREE3 这个题,发现我竟然还没做。感觉树剖或者倍增的做法也太平凡了,没啥写的欲望。我灵机一动,想出了一个单根做法。这也太喵了!我立马去看了 QTREE 系列的其它题,快速口糊了几个发现应该都能单根,而且题解区竟然没有一个人跟我想得一样!

那还说啥了,花了一天时间把 QTREE1 到 QTREE7 全通关了。给大家分享一下我的做法喵。

首先声明一下,SPOJ 的评测机真的奇慢无比,我 luogu 上跑 \text{600ms} 的 QTREE3 在 SPOJ 上 \text{2s} 没过。基本上所有题的 dfs 都要改成栈模拟,有点影响观感,所以我下面放的所有代码都是卡常之前的,直接在 SPOJ 上提交是过不了的喵。

以及,以下的做法不论是时间复杂度还是常数基本上都是最劣解,大家看个乐呵就好,千万别学喵(逃。如果能学到有用的东西再好不过啦!

题目的排序方式是按照主观难度升序排序的。所有题的输入都是我约定的简写,实际输入格式请按照原题面。

二、QTREE2

1、题目链接

luogu RMJ 链接

SPOJ 链接

2、题意简述

给定一棵 n 个节点的树,边带边权。请维护以下两种操作:

3、思路简析

没有修改操作,儿简送。第一个操作也太简单了,直接预处理一个以 1 为根的树中每个点到根节点的路径长度。设这个长度是 dis_i,那么 x 到 y 的路径长度就是 dis_x+dis_y-2dis_{\text{lca}(x,y)}。用你喜欢的方法求 \text{lca} 即可。

考虑维护一下第二个操作。如果我们能把一棵树像序列一样分成若干块,每一块的大小接近 \sqrt n,就可以预处理每个块的信息再合并了。

这里,我们有一种很经典的分块方法:

设 B=\sqrt n。维护一个桶,记录每个 dep_u\bmod B 的出现次数。在 0,\ldots,B-1 中选一个出现次数最少的余数 k。那么,我们选取所有 dep_u\bmod B=k 的节点 u 作为关键点。

根据鸽巢原理,此时选出的关键点个数一定小于等于 \frac{N}{B}。并且显而易见一个关键点与它最近的严格关键祖先之间距离不超过 B。所以任意一个点暴力向上跳最多 B 步就可以跳到一个关键点或者跳出这颗树。

此时,我们把连接两个关键点的一条链叫做一个块。如下图:

为方便画图,我们假设 B=3。图中所有的红色点就是关键点,标颜色的边就是一个“块”。图中有未画出的块(如 1-18)。不同块可能有重叠。

对于每个块,我们预处理出这个块内有几个点。对于查询操作,我们把一条路径拆成两条链,先看第 k 个点到底是在 x 到 \text{lca} 的链上还是在 y 到 \text{lca} 的链上。然后暴力向上跳到第一关键点,再一个关键点一个关键点往上跳。先算出还要向上走几条边,每跳一个整块就扣掉对应步数;某一块的大小已经大于 k 时,继续暴力跳完剩下的部分。加上 \text{lca} 的预处理,时间复杂度 O(n\log n+qB+\frac{qn}{B})。取 B=\sqrt n 即可。

写代码的时候脑子不太清醒喵,把第一个操作也顺手写上了。看笨蛋喵。

:::success[核心代码]

ll t,n,u,v,w,k,cs,Qtot,tot;
ll dep[N],b[N],dist[N],fa[N],up[N][Lg],id[N],near[N],wt[N],W[N],sz[N];
vector<pair<ll,ll> > e[N];
string s;

inline void Clear(){

    for(int i=1;i<=n;i++) b[i]=dist[i]=W[i]=sz[i]=id[i]=0,e[i].clear();
    for(int i=1;i<=n;i++) for(int j=0;j<Lg;j++) up[i][j]=0;

    return tot=b[0]=0,void();
}

inline void dfs1(ll u,ll f){

    dep[u]=dep[f]+1,fa[u]=up[u][0]=f,b[dep[u]%B]++;
    for(auto [v,w]:e[u]) if(v!=f) wt[v]=w,dist[v]=dist[u]+w,dfs1(v,u);

    return;
}

inline void dfs2(ll u){

    if(dep[u]%B==cs) id[u]=++tot;
    near[u]=(id[u]?u:near[fa[u]]);

    for(auto [v,w]:e[u]) if(v!=fa[u]) dfs2(v);

    return;
}

inline void build(){

    for(int i=1;i<=n;i++) if(id[i]){

        W[id[i]]=sz[id[i]]=0;
        ll p=near[fa[i]];

        for(int j=i;j!=p;j=fa[j]) W[id[i]]+=wt[j],sz[id[i]]++;
    }

    return;
}

inline ll lca(ll u,ll v){

    if(dep[u]<dep[v]) swap(u,v);

    ll k=dep[u]-dep[v];
    for(int j=Lg-1;~j;j--) if((k>>j)&1) u=up[u][j];

    if(u==v) return u;

    for(int j=Lg-1;~j;j--) if(up[u][j]!=up[v][j]) u=up[u][j],v=up[v][j];
    return fa[u];
}

inline ll query(ll u,ll v){

    ll ans=0,now=u;

    if(dep[near[u]]<=dep[v]){

        while(now!=v) ans+=wt[now],now=fa[now];
        return ans;
    }

    while(!id[now]) ans+=wt[now],now=fa[now];
    while(dep[near[fa[now]]]>dep[v]) ans+=W[id[now]],now=near[fa[now]];
    while(now!=v) ans+=wt[now],now=fa[now];

    return ans;
}

inline ll query2(ll u,ll k){

    ll ans=u;

    if(dep[u]-dep[near[u]]>=k){

        while(k--) ans=fa[ans];
        return ans;
    }

    while(!id[ans]) ans=fa[ans],k--;
    while(dep[ans]-dep[near[fa[ans]]]<k) k-=sz[id[ans]],ans=near[fa[ans]];
    while(k--) ans=fa[ans];

    return ans;
}

int main(){

    read(t);
    while(t--){

        read(n);
        for(int i=1;i<n;i++) read(u),read(v),read(w),e[u].push_back({v,w}),e[v].push_back({u,w});

        dfs1(1,0),cs=min_element(b,b+B)-b,dfs2(1);
        for(int j=1;j<Lg;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];

        build();

        for(Qtot=1;;Qtot++){

            read(s);
            if(s=="DONE") break;

            if(s=="DIST"){

                read(u),read(v);
                ll _lca=lca(u,v);

                if(u==v) write(0,'\n');
                else if(_lca==u) write(query(v,u),'\n');
                else if(_lca==v) write(query(u,v),'\n');
                else write(query(u,_lca)+query(v,_lca),'\n');
            }
            else{

                read(u),read(v),read(k);
                ll p=lca(u,v),du=dep[u]-dep[p],dv=dep[v]-dep[p];

                if(k<=du+1) write(query2(u,k-1),'\n');
                else write(query2(v,du+dv+1-k),'\n');
            }
        }

        pc('\n'),Clear();
    }

    return 0;
}

:::

三、QTREE5

1、题目链接

luogu RMJ 链接

SPOJ 链接

2、题意简述

给定一棵 n 个节点的树,点有黑白两个颜色。请维护以下两种操作:

3、思路简析

单点修改一定要想想操作序列分块喵。

我们考虑操作序列分块。操作序列分块是一种套路,常见写法是设定一个阈值 B,攒够 B 个操作后统一处理。

对于这道题,我们把操作暂存下来,存到 B 个后统一处理。对于这 B 个操作中所有修改操作涉及到的点,我们叫做不确定点,其它的点叫做确定点。

对于一次查询,我们分两种情况:答案所对应的白点是确定点或是不确定点。

所有确定点的颜色一定不会发生变化。那么原来是白色的点现在也一定是白色。以所有确定白点为源,在整棵原树上做多源 BFS 即可求出每个点到距离其最近的确定白点的距离。这一部分预处理时间复杂度 O(n),查询 O(1)。

因为我们只存了 B 个操作,所以最多有 B 个不确定的点。我们暴力遍历所有的不确定点并判断它们现在是不是白点即可。如果是白色,更新答案。这里需要一个 O(1) 求 \text{lca},不了解的小猫可以去学一下喵。这一部分不需要预处理,查询时间复杂度 O(B)。

加上 \text{lca} 的预处理,总时间复杂度为 O(n\log n+\frac{nq}{B}+qB)。取 B=\sqrt n 即可。卡常的话,需要把 BFS 换成换根 DP。

:::success[核心代码]

ll n,u,v,q,x[N],op[N],dep[N],fst[N],st[Lg][N<<1],dis[N],T,num;
vector<ll> e[N],tmp;
bool used[N],col[N];
queue<ll> Q;

inline ll mn(ll u,ll v){return dep[u]<dep[v]?u:v;}

inline void dfs1(ll u,ll f){

    dep[u]=dep[f]+1,fst[u]=++T,st[0][T]=u;
    for(auto v:e[u]) if(v!=f) dfs1(v,u),st[0][++T]=u;

    return;
}

inline void init(){

    for(int j=1;(1<<j)<=T;j++) for(int i=1;i+(1<<j)-1<=T;i++) st[j][i]=mn(st[j-1][i],st[j-1][i+(1<<(j-1))]);
    return;
}

inline ll lca(ll u,ll v){

    ll l=fst[u],r=fst[v];
    if(l>r) swap(l,r);

    ll k=__lg(r-l+1);
    return mn(st[k][l],st[k][r-(1<<k)+1]);
}

inline void rebuild(){

    for(int i=1;i<=n;i++) dis[i]=inf;
    for(int i=1;i<=n;i++) if(col[i]&&!used[i]) Q.push(i),dis[i]=0;

    while(!Q.empty()){

        ll u=Q.front();Q.pop();
        for(auto v:e[u]) if(dis[v]==inf) dis[v]=dis[u]+1,Q.push(v);
    }

    return;
}

inline ll query(ll u){

    if(col[u]) return 0;

    ll ans=dis[u];
    for(auto v:tmp) if(col[v]) ans=min(ans,dep[u]+dep[v]-2*dep[lca(u,v)]);

    return ans==inf?-1:ans;
}

int main(){

    read(n);
    for(int i=1;i<n;i++) read(u),read(v),e[u].push_back(v),e[v].push_back(u);

    dfs1(1,0),init();

    read(q);
    for(int i=1;i<=q;i++) read(op[i]),read(x[i]);

    for(int l=1;l<=q;l+=B){

        ll r=min(l+B-1,q);

        tmp.clear();
        for(int i=l;i<=r;i++) if(!op[i]&&!used[x[i]]) used[x[i]]=true,tmp.push_back(x[i]);

        rebuild();

        for(int i=l;i<=r;i++){

            if(!op[i]) num-=col[x[i]],col[x[i]]^=1,num+=col[x[i]];
            else write(num?query(x[i]):-1,'\n');
        }

        for(int i=l;i<=r;i++) used[x[i]]=false;
    }

    return 0;
}

:::

四、QTREE3

1、题目链接

luogu 主题库链接

SPOJ 链接

2、题意简述

给定一棵 n 个节点的树,点有黑白两个颜色。请维护以下两种操作:

3、思路简析

我们还是采用 QTREE2 的思路,按照深度模 B 选出一些关键点。

然后,我们考虑对每个块维护一个 vector,表示这个块内所有黑色的点。按深度排好序。

对于一个查询操作,我们暴力向上跳到离它最近的关键点,顺便更新答案;再在当前节点到根节点的所有块的 vector 的第一个元素里选一个深度最小的即可。

我们发现单点修改要修改一个子树中所有关键点的 vector,时间复杂度还是不对。所以要考虑操作序列分块。

把修改操作暂存起来。每存 P 个操作就统一处理。相似的,我们把这 P 个操作中所有修改操作涉及到的点称为不确定点,其它点称为确定点。

处理 P 个操作时,对于一次查询操作,遍历 vector 时取第一个确定的黑色节点。因为最多有 P 个节点颜色被更新,所以一次查询合计最多会跳过 P 个节点。

现在只需要额外考虑所有查询时为黑色的不确定点。判断当前询问的点在不在它的子树内即可。

暴力重构是简单的,一共至多 \frac{N}{B} 个关键点,每个块长为 B,时间复杂度就是 O(n)。

总时间复杂度为 O(\frac{qn}{P}+\frac{qn}{B}+qP+qB),取 B=P=\sqrt n 就可以了。

:::success[核心代码]

ll n,q,op,x,u,v,fa[N],id[N],dep[N],tung[N],near[N],cs,tot,dfn[N],sz[N],T;
vector<pair<ll,ll> > Dep;
vector<ll> e[N],S[N/B+10],cg;
bool col[N];

inline void dfs1(ll u,ll f){

    dep[u]=dep[f]+1,tung[dep[u]%B]++,dfn[u]=++T,sz[u]=1,fa[u]=f;
    for(auto v:e[u]) if(v!=f) dfs1(v,u),sz[u]+=sz[v];

    return;
}

inline void dfs2(ll u){

    if(dep[u]%B==cs) id[u]=++tot;
    near[u]=id[u]?u:near[fa[u]];

    for(auto v:e[u]) if(v!=fa[u]) dfs2(v);

    return;
}

inline ll query(ll u){

    ll Ans=-1,v=near[u];
    for(int i=u;i!=v;i=fa[i]) if(col[i]) Ans=i;

    for(int i=v;i;i=near[fa[i]]) for(auto x:S[id[i]]) if(col[x]){Ans=x;break;}

    for(auto x:cg) if(col[x]&&dfn[x]<=dfn[u]&&dfn[x]+sz[x]>dfn[u]&&(Ans==-1||dep[x]<dep[Ans])) Ans=x;

    return Ans;
}

inline void rebuild(){

    cg.clear();

    for(int i=1;i<=n;i++) if(id[i]){

        ll op=near[fa[i]];
        S[id[i]].clear();

        for(int j=i;j!=op;j=fa[j]) if(col[j]) S[id[i]].push_back(j);
        reverse(S[id[i]].begin(),S[id[i]].end());
    }

    return;
}

int main(){

    read(n),read(q);
    for(int i=1;i<n;i++) read(u),read(v),e[u].push_back(v),e[v].push_back(u);

    dfs1(1,0),cs=min_element(tung,tung+B)-tung,dfs2(1);

    while(q--){

        read(op),read(x);
        if(op==0) col[x]^=1,cg.push_back(x);
        else write(query(x),'\n');

        if(cg.size()>=B) rebuild();
    }

    return 0;
}

:::

五、QTREE1

1、题目链接

luogu RMJ 链接

luogu 主题库链接

SPOJ 链接

2、题意简述

给定一棵 n 个节点的树,边带边权。请维护以下两种操作:

3、思路简析

首先随便选一个点当作根节点,把所有边的边权放到它的儿子节点上,当作它儿子节点的点权即可。下面都称边权为点权。

相似的,我们还是按照深度模 B 选出一些关键点,并操作序列分块。

我们暂存 P 个操作并统一处理。对于这 P 个操作中所有修改操作涉及到的点,我们称为不确定点,其它点称为确定点。

预处理时,我们对于每一块预处理出当前块内所有确定点的点权最大值。

那么对于一次查询,只需要把路径拆成两条链,分别查询两条链上确定点的点权最大值,再暴力遍历所有不确定点,更新答案即可。枚举不确定点时,只考虑在 x 到 y 的路径上且不等于 \text{lca} 的点

查询链上的确定点的点权最大值和上面的做法差不多,只需要暴力遍历两端不完整的块,中间完整的块用提前预处理好的值即可。一定要注意边权转成点权之后要排除 \text{lca} 的点权。

时间复杂度为 O(\frac{qn}{P}+\frac{qn}{B}+qP+qB),还是取 B=P=\sqrt n 就行。

:::success[核心代码]

struct Querys{ll op,x,y;}q[N];
ll t,n,u[N],v[N],w[N],dfn[N],T,sz[N],dep[N],bl[N],L[N],R[N],ans[N];
ll fa[N],id[N],tot,near[N],b[N],wt[N],chs,qtot,up[N][Lg];
vector<pair<ll,ll> > e[N];
vector<ll> tmp;
bool vis[N];
string s;

inline void dfs1(ll u,ll f){

    dfn[u]=++T,sz[u]=1,fa[u]=f,dep[u]=dep[f]+1,b[dep[u]%B]++;
    for(auto [v,_w]:e[u]) if(v!=f) wt[v]=_w,dfs1(v,u),sz[u]+=sz[v];

    return;
}

inline void dfs2(ll u){

    if(dep[u]%B==chs) id[u]=++tot;
    near[u]=(id[u]?u:near[fa[u]]);

    for(auto [v,_w]:e[u]) if(v!=fa[u]) dfs2(v);
    return;
}

inline ll lca(ll x,ll y){

    if(dep[x]<dep[y]) swap(x,y);

    ll p=dep[x]-dep[y];
    for(int j=Lg-1;~j;j--) if((p>>j)&1) x=up[x][j];

    if(x==y) return x;

    for(int j=Lg-1;~j;j--) if(up[x][j]!=up[y][j]) x=up[x][j],y=up[y][j];
    return fa[x];
}

inline void rebuild(){

    for(int i=1;i<=n;i++) if(id[i]){

        ll fi=near[fa[i]];ans[id[i]]=0;
        for(int j=i;j!=fi;j=fa[j]) if(!vis[j]) ans[id[i]]=max(ans[id[i]],wt[j]);
    }

    return;
}

inline ll query(ll u,ll v){

    ll Ans=0,now=u;

    if(dep[near[u]]<dep[v]) for(int i=u;i!=v;i=fa[i]) Ans=max(Ans,(vis[i]?0:wt[i]));
    else{

        while(!id[now]) Ans=max(Ans,(vis[now]?0:wt[now])),now=fa[now];
        while(dep[near[fa[now]]]>dep[v]) Ans=max(Ans,ans[id[now]]),now=near[fa[now]];
        while(now!=v) Ans=max(Ans,(vis[now]?0:wt[now])),now=fa[now];
    }

    for(auto x:tmp) if((dfn[x]>dfn[v])&&(dfn[x]<dfn[v]+sz[v])&&(dfn[u]>=dfn[x])&&(dfn[u]<dfn[x]+sz[x])) Ans=max(Ans,wt[x]);

    return Ans;
}

inline void Clear(){

    for(int i=1;i<=n;i++) dfn[i]=b[i]=wt[i]=near[i]=id[i]=fa[i]=ans[i]=sz[i]=dep[i]=vis[i]=0,e[i].clear();
    return T=tot=b[0]=0,tmp.clear(),void();
}

int main(){

    read(t);
    while(t--){

        read(n);
        for(int i=1;i<n;i++){

            read(u[i]),read(v[i]),read(w[i]);
            e[u[i]].push_back({v[i],w[i]});
            e[v[i]].push_back({u[i],w[i]});
        }

        dfs1(1,0),chs=min_element(b,b+B)-b,dfs2(1);

        for(int i=1;i<=n;i++) up[i][0]=fa[i];
        for(int j=1;j<Lg;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];

        for(qtot=1;;qtot++){

            read(s);
            if(s=="DONE") break;
            else if(s=="QUERY") q[qtot].op=1;
            else q[qtot].op=2;

            read(q[qtot].x),read(q[qtot].y);
        }

        qtot--;
        for(int i=1;i<=qtot;i++) bl[i]=(i-1)/B+1;
        for(int i=1;i<=bl[qtot];i++) L[i]=R[i-1]+1,R[i]=min(qtot,i*B);

        for(int Qid=1;Qid<=bl[qtot];Qid++){

            tmp.clear();
            for(int i=1;i<=n;i++) vis[i]=false;

            ll l=L[Qid],r=R[Qid];
            for(int i=l;i<=r;i++) if(q[i].op==2){

                ll U=u[q[i].x],V=v[q[i].x];
                if(dep[U]<dep[V]) swap(U,V);

                if(!vis[U]) tmp.push_back(U);
                vis[U]=true;
            }

            rebuild();

            for(int i=l;i<=r;i++){

                if(q[i].op==2){

                    ll U=u[q[i].x],V=v[q[i].x];
                    if(dep[U]<dep[V]) swap(U,V);
                    wt[U]=q[i].y;
                }
                else{

                    ll _lca=lca(q[i].x,q[i].y);

                    if(q[i].x==q[i].y) write(0,'\n');
                    else if(_lca==q[i].y) write(query(q[i].x,q[i].y),'\n');
                    else if(_lca==q[i].x) write(query(q[i].y,q[i].x),'\n');
                    else write(max(query(q[i].x,_lca),query(q[i].y,_lca)),'\n');
                }
            }
        }

        Clear();
    }

    return 0;
}

:::

六、QTREE6

1、题目链接

luogu RMJ 链接

SPOJ 链接

2、题意简述

给定一棵 n 个节点的树,点带黑白两种颜色。请维护以下两种操作:

3、思路简析

此时,查询操作来到了连通块上。再树分块就不合适了。因为这种树分块只能处理链上的信息,不能处理连通块信息。

我们还是考虑操作序列分块。暂存操作,每 B 个操作统一处理。

统一处理 B 个操作时,我们把这些操作中所有修改操作涉及到的点称为不确定点,其它点称为确定点。

现在,我们将所有由确定点诱导的同色连通块集合缩成一个点,并在所有性质不同的点集之间,以及两个不确定点之间连一条边。其中一个点集的性质,指它是确定的,还是不确定的。如图:

右图是缩点后的样子。

那么对于一个确定点集,我们分情况讨论:

  1. 它的度数为 0,即孤立点集。从它开始不可能走到其它集合里。
  2. 它的度数为 1,即叶子点集。此时我们对于所有不确定点,维护一个 sum_0 和 sum_1,分别表示它的所有儿子节点中,黑色叶子点集的大小之和,以及所有白色叶子点集的大小之和。
  3. 它的度数至少为 2。此时保留这整个块,不做任何处理。

经典的,此时图中最多有 2B 个节点。证明如下:

缩点和删边之后是一片森林。设有 k 个不确定点,保留了 s 个固定块。每个保留的固定块度数至少为 2,所以小图至少有 2s 条边。另一方面,非空森林至多有 k+s-1 条边。于是 2s\le k+s-1,即 s\le k-1。

又因为不确定点的数量最多是 B 个,所以现在图中最多有 2B 个节点,证毕。

那么对于每次询问,暴力 DFS 到相邻颜色的连通块即可。每次遍历到不确定点,记得加上叶子点集的集合大小。

如果查询的节点已经被折叠(情况 2),需要特判。

时间复杂度 O(\frac{nq}{B}+qB),取 B=\sqrt n 即可。由于这是一颗树,缩点的精细实现并不需要并查集,可以节约常数。

:::success[核心代码]

ll n,m,u,v,T,tot,op[N],x[N],dfn[N],fa[N],par[N];
ll rep[N],sz[N],deg[N],bel[N],sum[N][2];
vector<ll> e[N],g[N],cg;
vector<pair<ll,ll> > Bp;
bool col[N],used[N];

inline void dfs1(ll u,ll f){

    fa[u]=f,dfn[u]=++T,par[T]=dfn[fa[u]];
    for(auto v:e[u]) if(v!=f) dfs1(v,u);

    return;
}

inline void add(ll u,ll v){return g[u].push_back(v),g[v].push_back(u),void();}

inline void rebuild(){

    tot=0,Bp.clear();
    for(int u=1;u<=n;u++){

        ll p=par[u];
        if(p&&!used[u]&&!used[p]&&col[u]==col[p]) rep[u]=rep[p];
        else{

            rep[u]=u,sz[u]=deg[u]=0,g[u].clear();
            if(used[u]) sum[u][0]=sum[u][1]=0;
        }

        sz[rep[u]]++;
        if(!p) continue;

        if(used[u]&&used[p]) add(u,p);
        else if(used[u]^used[p]){

            ll v=(used[u]?rep[p]:rep[u]),w=(used[u]?u:p);
            deg[v]++,bel[v]=w,Bp.push_back({v,w});
        }   
    }

    for(auto [v,w]:Bp){

        if(deg[v]==1) sum[w][col[v]]+=sz[v];
        else add(v,w);
    }

    return;
}
inline ll dfs2(ll u,ll f){

    ll ans=(used[u]?1+sum[u][col[u]]:sz[u]);
    for(auto v:g[u]) if(v!=f&&col[v]==col[u]) ans+=dfs2(v,u);

    return ans;
}

inline ll query(ll u){

    ll v=rep[u];
    if(used[u]||deg[v]>=2) return dfs2(v,0);
    if(deg[v]==0||col[v]!=col[bel[v]]) return sz[v];
    return dfs2(bel[v],0);
}

int main(){

    read(n);
    for(int i=1;i<n;i++) read(u),read(v),e[u].push_back(v),e[v].push_back(u);

    dfs1(1,0);

    read(m);
    for(int i=1;i<=m;i++) read(op[i]),read(x[i]),x[i]=dfn[x[i]];

    for(int l=1;l<=m;l+=B){

        ll r=min(l+B-1,m);

        cg.clear();
        for(int i=l;i<=r;i++) if(op[i]&&!used[x[i]]) used[x[i]]=true,cg.push_back(x[i]);

        rebuild();

        for(int i=l;i<=r;i++){

            if(op[i]) col[x[i]]^=1;
            else write(query(x[i]),'\n');
        }

        for(auto x:cg) used[x]=false;
    }

    return 0;
}

:::

七、QTREE7

1、题目链接

luogu RMJ 链接

SPOJ 链接

2、题意简述

给定一棵 n 个节点的树,点带黑白两种颜色以及点权。请维护以下三种操作:

3、思路简析

跟上一个题一模一样。把上一个题维护的集合大小信息全部换成点权最大值即可。要注意翻色或修改点权的点都算不确定点。以及空集合的最大值用 -\infty 表示,因为点权可以为负。

:::success[核心代码]

ll n,m,u,v,T,p,tot,a[N],w[N],val[N],op[N],x[N],dfn[N],fa[N],par[N];
ll rep[N],mx[N],deg[N],bel[N],best[N][2];
vector<ll> e[N],g[N],cg;
vector<pair<ll,ll> > Bp;
bool col[N],used[N];

inline void dfs1(ll u,ll f){

    fa[u]=f,dfn[u]=++T,par[T]=dfn[fa[u]];
    for(auto v:e[u]) if(v!=f) dfs1(v,u);

    return;
}

inline void add(ll u,ll v){return g[u].push_back(v),g[v].push_back(u),void();}

inline void rebuild(){

    tot=0,Bp.clear();
    for(int u=1;u<=n;u++){

        ll p=par[u];
        if(p&&!used[u]&&!used[p]&&col[u]==col[p]) rep[u]=rep[p];
        else{

            rep[u]=u,mx[u]=-inf,deg[u]=0,g[u].clear();
            if(used[u]) best[u][0]=best[u][1]=-inf;
        }

        mx[rep[u]]=max(mx[rep[u]],val[u]);
        if(!p) continue;

        if(used[u]&&used[p]) add(u,p);
        else if(used[u]^used[p]){

            ll v=(used[u]?rep[p]:rep[u]),w=(used[u]?u:p);
            deg[v]++,bel[v]=w,Bp.push_back({v,w});
        }   
    }

    for(auto [v,w]:Bp){

        if(deg[v]==1) best[w][col[v]]=max(best[w][col[v]],mx[v]);
        else add(v,w);
    }

    return;
}
inline ll dfs2(ll u,ll f){

    ll ans=(used[u]?max(val[u],best[u][col[u]]):mx[u]);
    for(auto v:g[u]) if(v!=f&&col[v]==col[u]) ans=max(ans,dfs2(v,u));

    return ans;
}

inline ll query(ll u){

    ll v=rep[u];
    if(used[u]||deg[v]>=2) return dfs2(v,0);
    if(deg[v]==0||col[v]!=col[bel[v]]) return mx[v];
    return dfs2(bel[v],0);
}

int main(){

    read(n);
    for(int i=1;i<n;i++) read(u),read(v),e[u].push_back(v),e[v].push_back(u);

    dfs1(1,0);
    for(int i=1;i<=n;i++) read(p),col[dfn[i]]=p;
    for(int i=1;i<=n;i++) read(val[dfn[i]]);

    read(m);
    for(int i=1;i<=m;i++){

        read(op[i]),read(x[i]),x[i]=dfn[x[i]];
        if(op[i]==2) read(w[i]);
    }

    for(int l=1;l<=m;l+=B){

        ll r=min(l+B-1,m);

        cg.clear();
        for(int i=l;i<=r;i++) if(op[i]&&!used[x[i]]) used[x[i]]=true,cg.push_back(x[i]);

        rebuild();

        for(int i=l;i<=r;i++){

            if(op[i]==1) col[x[i]]^=1;
            else if(op[i]==2) val[x[i]]=w[i];
            else write(query(x[i]),'\n');
        }

        for(auto x:cg) used[x]=false;
    }

    return 0;
}

:::

八、QTREE4

1、题目链接

luogu RMJ 链接

luogu 主题库链接

SPOJ 链接

2、题意简述

给定一棵 n 个节点的树,边带边权(可负),点带黑白两种颜色。请维护以下两种操作:

3、思路简析

有点懵,但是不管了,先操作序列分块了再说。

暂存操作,每 B 个操作统一处理。

统一处理 B 个操作时,我们把这些操作中所有修改操作涉及到的点称为不确定点,其它点称为确定点。

对于一次查询,我们将答案对应的两个白点分成三种情况:

  1. 两个点都是确定点。可以先提前做一次树形 DP 求出。
  2. 其中一个点是不确定点。我们提前用树形 DP 预处理出距离每个点最远的确定白点的距离。此时因为我们存了 B 个操作,所以最多有 B 个不确定点。暴力遍历所有不确定点,查表更新答案即可。时间复杂度 O(B)。
  3. 两个点都是不确定点。我们把所有不确定点单独拿出来建一棵虚树,边权为原树上路径的边权和,再做一次 DP 求出此时的直径即可。时间复杂度 O(B)。

每批操作建一次虚树,每次查询跑一次 DP。建虚树时每批要按 DFS 序排序,O(B\log B) 的建树开销会在 B=\Theta(\sqrt n) 时被该批的 O(n) 预处理吸收。

总时间复杂度 O(\frac{nq}{B}+qB),取 B=\sqrt n 即可。

:::success[核心代码]

ll n,q,T,cnt,fans,ans,u,v,w;
ll fa[N],dfn[N],sz[N],dis[N],up[N][Lg],op[Q],dep[N];
ll down[N],sec[N],son[N],Up[N];
bool wh[N],vis[N];
char c;

vector<pair<ll,ll> > e[N];
vector<vector<ll> > ve;
vector<ll> a,vfa,vw;

inline void dfs1(ll u,ll f){

    fa[u]=f,dfn[u]=++T,sz[u]=1,dep[u]=dep[f]+1;
    for(auto [v,w]:e[u]) if(v!=f) dis[v]=dis[u]+w,dfs1(v,u),sz[u]+=sz[v];

    return;
}

inline ll lca(ll u,ll v){

    if(dep[u]<dep[v]) swap(u,v);

    ll k=dep[u]-dep[v];
    for(int j=Lg-1;~j;j--) if((k>>j)&1) u=up[u][j];

    if(u==v) return u;

    for(int j=Lg-1;~j;j--) if(up[u][j]!=up[v][j]) u=up[u][j],v=up[v][j];
    return fa[u];
}

inline void dfsD(ll u){

    down[u]=(wh[u]&&!vis[u]?0:-inf),sec[u]=-inf,son[u]=0;
    fans=max(fans,down[u]);

    for(auto [v,w]:e[u]) if(v!=fa[u]){

        dfsD(v);
        if(down[v]==-inf) continue;

        ll t=down[v]+w;
        if(down[u]!=-inf) fans=max(fans,down[u]+t);

        if(t>down[u]) sec[u]=down[u],down[u]=t,son[u]=v;
        else sec[u]=max(sec[u],t);
    }

    return;
}

inline void dfsU(ll u){

    for(auto [v,w]:e[u]) if(v!=fa[u]){

        ll t=max(Up[u],(son[u]==v?sec[u]:down[u]));
        Up[v]=(t==-inf?-inf:t+w);

        dfsU(v);
    }

    return;
}

inline void build(){

    sort(a.begin(),a.end(),[](const ll &u,const ll &v){return dfn[u]<dfn[v];});

    ll m=a.size();
    for(int i=1;i<m;i++) a.push_back(lca(a[i-1],a[i]));

    sort(a.begin(),a.end(),[](const ll &u,const ll &v){return dfn[u]<dfn[v];});
    a.erase(unique(a.begin(),a.end()),a.end());

    vfa.resize(a.size()),vw.resize(a.size()),ve.clear(),ve.resize(a.size());

    for(int i=1;i<(ll)a.size();i++){

        ll f=i-1;
        while(dfn[a[i]]<dfn[a[f]]||dfn[a[i]]>=dfn[a[f]]+sz[a[f]]) f=vfa[f];
        vfa[i]=f,vw[i]=dis[a[i]]-dis[a[f]],ve[f].push_back(i);
    }

    return;
}

inline ll DP(ll x){

    ll u=a[x],mx=-inf;
    if(vis[u]&&wh[u]) mx=0,ans=max(ans,max(Up[u],down[u]));

    for(int i:ve[x]){

        ll t=DP(i);
        if(t==-inf) continue;

        t+=vw[i];
        if(mx!=-inf) ans=max(ans,mx+t);
        mx=max(mx,t);
    }

    return mx;
}

int main(){

    read(n);
    for(int i=1;i<n;i++) read(u),read(v),read(w),e[u].push_back({v,w}),e[v].push_back({u,w});

    dfs1(1,0);
    for(int i=1;i<=n;i++) up[i][0]=fa[i];
    for(int j=1;j<Lg;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];

    read(q);
    for(int i=1;i<=q;i++){

        read(c);
        if(c=='C') read(op[i]);
    }

    cnt=n;
    for(int i=1;i<=n;i++) wh[i]=true;

    a.reserve(2*B);
    for(int l=1;l<=q;l+=B){

        ll r=min(q,l+B-1);
        bool flag=false,cf=false;
        a.clear();

        for(int i=l;i<=r;i++){

            if(!op[i]) flag=true;
            else if(!vis[op[i]]) vis[op[i]]=true,a.push_back(op[i]);
        }

        if(flag) fans=Up[1]=-inf,dfsD(1),dfsU(1),build();

        for(int i=l;i<=r;i++){

            if(op[i]) cnt+=(wh[op[i]]?-1:1),wh[op[i]]^=1,cf=false;
            else if(!cnt) ps("They have disappeared.\n");
            else{

                if(!cf){

                    ans=max(0,fans),cf=true;
                    if(!a.empty()) DP(0);
                }

                write(ans,'\n');
            }
        }

        for(auto u:a) vis[u]=false;
    }

    return 0;
}

:::