SPOJ QTREE 系列简要题解

博主： M_sea
发布时间：2019 年 08 月 04 日
3456次浏览
4 条评论
23193字数
分类：题解

QTREE1

把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了...

但是注意查询时 LCA 是不能查的，需要判一下。

而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQ

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#define re register
#define swap(x,y) { int tmp=x; x=y; y=tmp; }

int max(int a,int b) { return a>b?a:b; }
int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

#define N (10000+10)

int n,val[N];

struct edge { int v,w,nxt; } e[N<<1];
int head[N],x[N],y[N],e_cnt=0;
void addEdge(int u,int v,int w) {
    ++e_cnt;
    e[e_cnt].v=v,e[e_cnt].w=w,e[e_cnt].nxt=head[u],head[u]=e_cnt;
}

int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],rl[N],tim=0;
void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==f) continue;
        val[v]=w,dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
void dfs2(int u,int anc) {
    dfn[u]=++tim,rl[tim]=u,top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}

#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2];
void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
void build(int o,int l,int r) {
    if (l==r) { maxv[o]=val[rl[l]]; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int p,int w) {
    if (l==r) { maxv[o]=w; return; }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    pushup(o);
}
int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return maxv[o];
    int mid=(l+r)>>1,res=0;
    if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
    return res;
}
#undef ls
#undef rs

int Query(int u,int v) {
    int tu=top[u],tv=top[v],res=0;
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) { swap(tu,tv); swap(u,v); }
        res=max(res,query(1,1,n,dfn[tu],dfn[u]));
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    res=max(res,query(1,1,n,dfn[v]+1,dfn[u]));
    return res;
}

void init() {
    n=e_cnt=tim=0;
    memset(head,0,sizeof(head));
    memset(hson,0,sizeof(hson));
    memset(top,0,sizeof(top));
    memset(maxv,0,sizeof(maxv));
}

int main() {
    int T=read();
    while (T--) {
        init();
        n=read();
        for (re int i=1;i<n;++i) {
            int u=read(),v=read(),w=read();
            x[i]=u,y[i]=v;
            addEdge(u,v,w),addEdge(v,u,w);
        }
        dfs1(1,0),dfs2(1,1); build(1,1,n);
        while (233) {
            char op[10]; scanf("%s",op);
            if (op[0]=='D') break;
            if (op[0]=='C') {
                int i=read(),w=read(),u=dep[x[i]]>dep[y[i]]?x[i]:y[i];
                modify(1,1,n,dfn[u],w);
            } else {
                int u=read(),v=read();
                if (u==v) puts("0");
                else printf("%d\n",Query(u,v));
            }
        }
    }
    return 0;
}

QTREE2

DIST 操作只需要维护树上前缀和即可求出答案。

KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即可求出。

所以只需要写一个倍增 LCA 和一个倍增找 $k$ 次祖先就好了。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n;

struct edge { int v,w,nxt; } e[N<<1];
int head[N],e_cnt=0;
inline void addEdge(int u,int v,int w) {
    e[++e_cnt]=(edge){v,w,head[u]},head[u]=e_cnt;
}

int dep[N],dis[N],f[14][N];
inline void dfs(int u,int fa) {
    for (re int i=1;i<=13;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa) continue;
        dep[v]=dep[u]+1,dis[v]=dis[u]+w,f[0][v]=u;
        dfs(v,u);
    }
}

inline int getLCA(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=13;~i;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (dep[u]!=dep[v]) u=f[0][u];
    for (re int i=13;~i;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    if (u!=v) u=f[0][u];
    return u;
}
inline int find(int u,int k) {
    for (re int i=13;~i;--i)
        if (k&(1<<i)) u=f[i][u];
    return u;
}

inline void init() {
    memset(head,0,sizeof(head)),e_cnt=0;
}

int main() {
    int T=read();
    while (T--) {
        init();
        n=read();
        for (re int i=1;i<n;++i) {
            int u=read(),v=read(),w=read();
            addEdge(u,v,w),addEdge(v,u,w);
        }
        dfs(1,0);
        while (233) {
            char op[10]; scanf("%s",op);
            if (op[1]=='O') break;
            if (op[0]=='D') {
                int u=read(),v=read(),t=getLCA(u,v);
                printf("%d\n",dis[u]+dis[v]-(dis[t]<<1));
            } else {
                int u=read(),v=read(),t=getLCA(u,v),k=read();
                int L=dep[u]-dep[t]+1,R=dep[v]-dep[t]+1;
                if (L>=k) printf("%d\n",find(u,k-1));
                else printf("%d\n",find(v,R-(k-L+1)));
            }
        }
    }
    return 0;
}

QTREE3

树链剖分，每条重链开一个 set 维护所有黑点。

修改直接 insert / erase ，查询就跳重链跳到根并更新答案即可。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,c[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],id[N],tim=0;
void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
void dfs2(int u,int anc) {
    dfn[u]=++tim,id[tim]=u,top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}

set<int> S[N];

int main() {
    n=read(),Q=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    while (Q--) {
        int op=read(),u=read();
        if (!op) {
            c[u]^=1;
            if (c[u]) S[top[u]].insert(dfn[u]);
            else S[top[u]].erase(dfn[u]);
        } else {
            int res=-1;
            while (u) {
                if (S[top[u]].size()) {
                    int v=id[*S[top[u]].begin()];
                    if (dep[v]<=dep[u]) res=v;
                }
                u=fa[top[u]];
            }
            printf("%d\n",res);
        }
    }
    return 0;
}

QTREE4

其实和捉迷藏那题是一样的...

首先建出点分树，然后每个点开两个堆，一个维护点分子树中所有白点到 $u$ 在点分树上父亲的距离，一个维护所有儿子的前一个堆的堆顶。

然后再开一个堆记一下所有点的最长链与次长链之和。那么就很好算答案了。

然后修改的话就在点分树上暴跳父亲并修改一些东西。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n;

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

struct Heap {
    priority_queue<int> Q,O;
    inline void push(int x) { Q.push(x); }
    inline void del(int x) { O.push(x); }
    inline void remove() {
        while (!O.empty()&&Q.top()==O.top()) Q.pop(),O.pop();
    }
    inline int size() { return Q.size()-O.size(); }
    inline void pop() { remove(); Q.pop(); }
    inline int top() { remove(); return Q.empty()?0:Q.top(); }
    inline int top2() {
        if (size()<2) return 0;
        int tmp=top(); pop(); int res=top();
        push(tmp); return res;
    }
} ans,A[N],B[N];

inline void push(Heap& x) { if (x.size()>1) ans.push(x.top()+x.top2()); }
inline void del(Heap& x) { if (x.size()>1) ans.del(x.top()+x.top2()); }

namespace OT {
    int lg[N<<2],pos[N<<1],st[19][N<<2],dep[N],dis[N],tot=0;
    inline void dfs(int u,int fa) {
        st[0][++tot]=u,pos[u]=tot;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w; if (v==fa) continue;
            dep[v]=dep[u]+1,dis[v]=dis[u]+w;
            dfs(v,u),st[0][++tot]=u;
        }
    }
    inline int cmp(int a,int b) { return dep[a]<dep[b]?a:b; }
    inline void init_rmq() {
        for (re int i=2;i<=tot;++i) lg[i]=lg[i>>1]+1;
        for (re int i=1;i<=18;++i)
            for (re int j=1;j+(1<<i)-1<=tot;++j)
                st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    }
    inline int getdis(int u,int v) {
        if (pos[u]>pos[v]) swap(u,v);
        int t=lg[pos[v]-pos[u]+1];
        int lca=cmp(st[t][pos[u]],st[t][pos[v]-(1<<t)+1]);
        return dis[u]+dis[v]-(dis[lca]<<1);
    }
    inline void init() { dfs(1,0); init_rmq(); }
}

namespace T {
    int sz[N],vis[N],fa[N];
    int sumsz,minsz,root;
    inline void getroot(int u,int pa) {
        sz[u]=1; int now=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==pa||vis[v]) continue;
            getroot(v,u),sz[u]+=sz[v];
            now=max(now,sz[v]);
        }
        now=max(now,sumsz-sz[u]);
        if (now<minsz) root=u,minsz=now;
    }
    inline void dfs(int u,int pa,int anc) {
        A[anc].push(OT::getdis(u,fa[anc]));
        for (re int i=head[u];i;i=e[i].nxt)
            if (e[i].v!=pa&&!vis[e[i].v]) dfs(e[i].v,u,anc);
    }
    inline void solve(int u,int pa) {
        vis[u]=1,fa[u]=pa;
        dfs(u,0,u),B[u].push(0),B[pa].push(A[u].top());
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==pa||vis[v]) continue;
            minsz=n,sumsz=sz[v]; getroot(v,u);
            solve(root,u);
        }
        push(B[u]);
    }
    inline void build() {
        root=0,minsz=sumsz=n;
        getroot(1,0); solve(root,0);
    }

    int col[N];
    inline void whiten(int u) {
        del(B[u]),B[u].push(0),push(B[u]);
        for (re int i=u;fa[i];i=fa[i]) {
            del(B[fa[i]]);
            if (A[i].size()) B[fa[i]].del(A[i].top());
            A[i].push(OT::getdis(u,fa[i]));
            B[fa[i]].push(A[i].top());
            push(B[fa[i]]);
        }
    }
    inline void blacken(int u) {
        del(B[u]),B[u].del(0),push(B[u]);
        for (re int i=u;fa[i];i=fa[i]) {
            del(B[fa[i]]);
            if (A[i].size()) B[fa[i]].del(A[i].top());
            A[i].del(OT::getdis(u,fa[i]));
            if (A[i].size()) B[fa[i]].push(A[i].top());
            push(B[fa[i]]);
        }
    }
    inline void query() {
        int Q=read(),num=n;
        while (Q--) {
            char op[2]; scanf("%s",op);
            if (op[0]=='A') {
                if (!num) puts("They have disappeared.");
                else if (num==1) puts("0");
                else printf("%d\n",max(0,ans.top()));
            } else {
                int u=read();
                if (col[u]) whiten(u),col[u]=0,++num;
                else blacken(u),col[u]=1,--num;
            }
        }
    }
}

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    OT::init(); T::build(); T::query();
    return 0;
}

QTREE5

显然可以动态点分治，但是这东西我再也不想写了...

考虑一个 LCT 做法。

每个节点维护一个 $lm$ 和 $rm$ ，分别表示该节点所在的 Splay 中最浅的/最深的节点能到的子树中最近的白点的距离。

考虑这个东西怎么维护。因为 $lm$ 和 $rm$ 类似，这里只考虑 $lm$ 。

显然 $lm_u$ 是以下两部分的最小值：

左子树的答案。
左子树的 $size$ + 右子树的答案 +1。

如果 $u$ 是白点的话，还要加上一部分：左子树的 $size$ 。

考虑怎么算右子树的答案。对每个节点维护一个 multiset ，维护所有虚子树的答案即可。

这个东西在 access 的时候顺便维护一下就好了。

查询就直接 makeroot ，然后查 $lm$ 就好了。

注意 makeroot 时需要 reverse ，而 reverse 时要把 $lm$ 和 $rm$ 也交换！

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,col[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

struct Link_Cut_Tree {
    int fa[N],ch[N][2],sz[N],rev[N];
    int lm[N],rm[N];
    multiset<int> S[N];
    int sta[N];
    inline int fir(int x) { return S[x].empty()?1e9:*(S[x].begin()); }
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void reverse(int x) {
        swap(ch[x][0],ch[x][1]),swap(lm[x],rm[x]),rev[x]^=1;
    }
    inline void pushup(int x) {
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
        lm[x]=min(lm[ch[x][0]],sz[ch[x][0]]+min(fir(x),lm[ch[x][1]]+1));
        if (col[x]) lm[x]=min(lm[x],sz[ch[x][0]]);
        rm[x]=min(rm[ch[x][1]],sz[ch[x][1]]+min(fir(x),rm[ch[x][0]]+1));
        if (col[x]) rm[x]=min(rm[x],sz[ch[x][1]]);
    }
    inline void pushdown(int x) {
        if (rev[x]) {
            if (ch[x][0]) reverse(ch[x][0]);
            if (ch[x][1]) reverse(ch[x][1]);
            rev[x]=0;
        }
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        int y=x,z=0; sta[++z]=y;
        while (nroot(y)) sta[++z]=y=fa[y];
        while (z) pushdown(sta[z--]);
        while (nroot(x)) {
            y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x]) {
            splay(x);
            S[x].insert(lm[ch[x][1]]+1);
            ch[x][1]=y;
            auto it=S[x].lower_bound(lm[ch[x][1]]+1);
            if (it!=S[x].end()&&*it==lm[ch[x][1]]+1) S[x].erase(it);
            pushup(x);
        }
    }
    inline void makeroot(int x) { access(x),splay(x),reverse(x); }
} T;

inline void dfs(int u,int f) {
    T.fa[u]=f;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        T.S[u].insert(1e9),T.pushup(u);
        dfs(v,u);
    }
}

int main() {
    T.lm[0]=T.rm[0]=1e9;
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0);
    Q=read();
    while (Q--) {
        int op=read(),u=read();
        if (!op) {
            T.makeroot(u);
            col[u]^=1,T.pushup(u);
        } else {
            T.makeroot(u);
            printf("%d\n",T.lm[u]>n?-1:T.lm[u]);
        }
    }
    return 0;
}

QTREE6

维护两个 LCT ，一棵维护白点，一棵维护黑点。每次修改暴力 cut 再 link 即可。

然而这样子会被菊花图卡爆。

考虑一种~~我不会~~的套路：把 $u$ 的颜色作为 $(u,fa_u)$ 边的颜色。

同样维护两个 LCT ，一棵维护白边，一棵维护黑边。

可以发现每次修改只需要在一棵树中 cut 掉父边，再在另一棵树中 link 父边即可。

查询就直接 findroot ，然后输出重儿子的大小即可。子树大小按照维护子树信息那一套维护。

一个要注意的地方：这棵树被我们强制成了有根树，所以不能 makeroot 。

另一个要注意的地方：根节点要建一个虚点当它的父节点，这样子根节点才会有父边。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,c[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

struct Link_Cut_Tree {
    int fa[N],ch[N][2],s[N],si[N];
    inline void init() { for (re int i=1;i<=n+1;++i) s[i]=1; }
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void pushup(int x) { s[x]=s[ch[x][0]]+s[ch[x][1]]+si[x]+1; }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        while (nroot(x)) {
            int y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x])
            splay(x),si[x]+=s[ch[x][1]],si[x]-=s[ch[x][1]=y];
    }
    inline int findroot(int x) {
        access(x),splay(x);
        while (ch[x][0]) x=ch[x][0];
        splay(x); return x;
    }
    inline void link(int x,int y) {
        splay(x),access(y),splay(y);
        fa[x]=y,si[y]+=s[x],s[y]+=s[x];
    }
    inline void cut(int x,int y) {
        access(x),splay(x);
        ch[x][0]=fa[ch[x][0]]=0;
        pushup(x);
    }
} T[2];

int fa[N];
inline void dfs(int u,int f) {
    fa[u]=f,T[0].link(u,f);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=f) dfs(e[i].v,u);
}

int main() {
    n=read(); T[0].init(),T[1].init();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,n+1);
    Q=read();
    while (Q--) {
        int op=read(),u=read();
        if (op) T[c[u]].cut(u,fa[u]),c[u]^=1,T[c[u]].link(u,fa[u]);
        else {
            int rt=T[c[u]].findroot(u);
            printf("%d\n",T[c[u]].s[T[c[u]].ch[rt][1]]);
        }
    }
    return 0;
}

QTREE7

和 QTREE6 差不多，每个节点开一个 multiset 维护虚儿子的最大值即可。

然后 link 的时候连虚边有点麻烦，可以直接连实边。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q;
int c[N],w[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

struct Link_Cut_Tree {
    int fa[N],ch[N][2],mx[N]; multiset<int> S[N];
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void pushup(int x) {
        mx[x]=max(w[x],max(mx[ch[x][0]],mx[ch[x][1]]));
        if (S[x].size()) mx[x]=max(mx[x],*S[x].rbegin());
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        while (nroot(x)) {
            int y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x]) {
            splay(x);
            if (ch[x][1]) S[x].insert(mx[ch[x][1]]);
            ch[x][1]=y;
            if (ch[x][1]) S[x].erase(mx[ch[x][1]]);
            pushup(x);
        }
    }
    inline int findroot(int x) {
        access(x),splay(x);
        while (ch[x][0]) x=ch[x][0];
        splay(x); return x;
    }
    inline void link(int x,int y) {
        splay(x),access(y),splay(y);
        fa[x]=y,ch[y][1]=x,pushup(y);
    }
    inline void cut(int x,int y) {
        access(x),splay(x);
        ch[x][0]=fa[ch[x][0]]=0;
        pushup(x);
    }
} T[2];

int fa[N];
inline void dfs(int u,int f) {
    fa[u]=f,T[c[u]].link(u,f);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=f) dfs(e[i].v,u);
}

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    for (re int i=1;i<=n;++i) c[i]=read();
    for (re int i=1;i<=n;++i) w[i]=read();
    T[0].mx[0]=T[1].mx[0]=-2e9; dfs(1,n+1);
    Q=read();
    while (Q--) {
        int op=read(),u=read();
        if (op==0) {
            int rt=T[c[u]].findroot(u);
            printf("%d\n",T[c[u]].mx[T[c[u]].ch[rt][1]]);
        } else if (op==1) {
            T[c[u]].cut(u,fa[u]),c[u]^=1,T[c[u]].link(u,fa[u]);
        } else {
            T[c[u]].access(u),T[c[u]].splay(u);
            w[u]=read(); T[c[u]].pushup(u);
        }
    }
    return 0;
}

最后修改：2019 年 09 月 27 日 01 : 42 PM

发表评论取消回复

评论 *

私密评论

名称 *

邮箱 *

地址

4 条评论

smy
July 28th, 2019 at 02:02 pm

显然可以动态点分治，但是这东西我再也不想写了...

真香

回复
1. M_sea
  July 28th, 2019 at 02:32 pm
  
  @smy
  
  我是这种人吗？是的
  
  回复
smy
July 27th, 2019 at 09:16 am

QTREE不应该写长链剖分球k级祖先吗

回复
1. M_sea
  July 27th, 2019 at 09:25 am
  
  @smy
  
  不会，告辞
  
  回复

洛谷5176 公约数
浏览次数: 25554
HNOI2019 ～Zero～
浏览次数: 25344
APIO2020 ～Intermezzo～
浏览次数: 14536
～After OI～
浏览次数: 14409
CSP2019 ～Idle Dream～
浏览次数: 9841

草莓奶昔
一直在研究这道题，难得有这么好的码风，感谢楼主!!!
konjacq
巨佬M_sea的AFO就是去搞ACM吗orz
xgzc
现在已经拿到满意的成绩了
Qihoo360
orz
智子
突然想起我小学时也是在白老师那里学的（

SPOJ QTREE 系列简要题解

M_sea • 2019 年 08 月 04 日

QTREE1

把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了...

但是注意查询时 LCA 是不能查的，需要判一下。

而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQ

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#define re register
#define swap(x,y) { int tmp=x; x=y; y=tmp; }

int max(int a,int b) { return a>b?a:b; }
int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

#define N (10000+10)

int n,val[N];

struct edge { int v,w,nxt; } e[N<<1];
int head[N],x[N],y[N],e_cnt=0;
void addEdge(int u,int v,int w) {
    ++e_cnt;
    e[e_cnt].v=v,e[e_cnt].w=w,e[e_cnt].nxt=head[u],head[u]=e_cnt;
}

int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],rl[N],tim=0;
void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==f) continue;
        val[v]=w,dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
void dfs2(int u,int anc) {
    dfn[u]=++tim,rl[tim]=u,top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}

#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2];
void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
void build(int o,int l,int r) {
    if (l==r) { maxv[o]=val[rl[l]]; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int p,int w) {
    if (l==r) { maxv[o]=w; return; }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    pushup(o);
}
int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return maxv[o];
    int mid=(l+r)>>1,res=0;
    if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
    return res;
}
#undef ls
#undef rs

int Query(int u,int v) {
    int tu=top[u],tv=top[v],res=0;
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) { swap(tu,tv); swap(u,v); }
        res=max(res,query(1,1,n,dfn[tu],dfn[u]));
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    res=max(res,query(1,1,n,dfn[v]+1,dfn[u]));
    return res;
}

void init() {
    n=e_cnt=tim=0;
    memset(head,0,sizeof(head));
    memset(hson,0,sizeof(hson));
    memset(top,0,sizeof(top));
    memset(maxv,0,sizeof(maxv));
}

int main() {
    int T=read();
    while (T--) {
        init();
        n=read();
        for (re int i=1;i<n;++i) {
            int u=read(),v=read(),w=read();
            x[i]=u,y[i]=v;
            addEdge(u,v,w),addEdge(v,u,w);
        }
        dfs1(1,0),dfs2(1,1); build(1,1,n);
        while (233) {
            char op[10]; scanf("%s",op);
            if (op[0]=='D') break;
            if (op[0]=='C') {
                int i=read(),w=read(),u=dep[x[i]]>dep[y[i]]?x[i]:y[i];
                modify(1,1,n,dfn[u],w);
            } else {
                int u=read(),v=read();
                if (u==v) puts("0");
                else printf("%d\n",Query(u,v));
            }
        }
    }
    return 0;
}

QTREE2

DIST 操作只需要维护树上前缀和即可求出答案。

KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即可求出。

所以只需要写一个倍增 LCA 和一个倍增找 $k$ 次祖先就好了。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n;

struct edge { int v,w,nxt; } e[N<<1];
int head[N],e_cnt=0;
inline void addEdge(int u,int v,int w) {
    e[++e_cnt]=(edge){v,w,head[u]},head[u]=e_cnt;
}

int dep[N],dis[N],f[14][N];
inline void dfs(int u,int fa) {
    for (re int i=1;i<=13;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa) continue;
        dep[v]=dep[u]+1,dis[v]=dis[u]+w,f[0][v]=u;
        dfs(v,u);
    }
}

inline int getLCA(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=13;~i;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (dep[u]!=dep[v]) u=f[0][u];
    for (re int i=13;~i;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    if (u!=v) u=f[0][u];
    return u;
}
inline int find(int u,int k) {
    for (re int i=13;~i;--i)
        if (k&(1<<i)) u=f[i][u];
    return u;
}

inline void init() {
    memset(head,0,sizeof(head)),e_cnt=0;
}

int main() {
    int T=read();
    while (T--) {
        init();
        n=read();
        for (re int i=1;i<n;++i) {
            int u=read(),v=read(),w=read();
            addEdge(u,v,w),addEdge(v,u,w);
        }
        dfs(1,0);
        while (233) {
            char op[10]; scanf("%s",op);
            if (op[1]=='O') break;
            if (op[0]=='D') {
                int u=read(),v=read(),t=getLCA(u,v);
                printf("%d\n",dis[u]+dis[v]-(dis[t]<<1));
            } else {
                int u=read(),v=read(),t=getLCA(u,v),k=read();
                int L=dep[u]-dep[t]+1,R=dep[v]-dep[t]+1;
                if (L>=k) printf("%d\n",find(u,k-1));
                else printf("%d\n",find(v,R-(k-L+1)));
            }
        }
    }
    return 0;
}

QTREE3

树链剖分，每条重链开一个 set 维护所有黑点。

修改直接 insert / erase ，查询就跳重链跳到根并更新答案即可。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,c[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],id[N],tim=0;
void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
void dfs2(int u,int anc) {
    dfn[u]=++tim,id[tim]=u,top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}

set<int> S[N];

int main() {
    n=read(),Q=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    while (Q--) {
        int op=read(),u=read();
        if (!op) {
            c[u]^=1;
            if (c[u]) S[top[u]].insert(dfn[u]);
            else S[top[u]].erase(dfn[u]);
        } else {
            int res=-1;
            while (u) {
                if (S[top[u]].size()) {
                    int v=id[*S[top[u]].begin()];
                    if (dep[v]<=dep[u]) res=v;
                }
                u=fa[top[u]];
            }
            printf("%d\n",res);
        }
    }
    return 0;
}

QTREE4

其实和捉迷藏那题是一样的...

首先建出点分树，然后每个点开两个堆，一个维护点分子树中所有白点到 $u$ 在点分树上父亲的距离，一个维护所有儿子的前一个堆的堆顶。

然后再开一个堆记一下所有点的最长链与次长链之和。那么就很好算答案了。

然后修改的话就在点分树上暴跳父亲并修改一些东西。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n;

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

struct Heap {
    priority_queue<int> Q,O;
    inline void push(int x) { Q.push(x); }
    inline void del(int x) { O.push(x); }
    inline void remove() {
        while (!O.empty()&&Q.top()==O.top()) Q.pop(),O.pop();
    }
    inline int size() { return Q.size()-O.size(); }
    inline void pop() { remove(); Q.pop(); }
    inline int top() { remove(); return Q.empty()?0:Q.top(); }
    inline int top2() {
        if (size()<2) return 0;
        int tmp=top(); pop(); int res=top();
        push(tmp); return res;
    }
} ans,A[N],B[N];

inline void push(Heap& x) { if (x.size()>1) ans.push(x.top()+x.top2()); }
inline void del(Heap& x) { if (x.size()>1) ans.del(x.top()+x.top2()); }

namespace OT {
    int lg[N<<2],pos[N<<1],st[19][N<<2],dep[N],dis[N],tot=0;
    inline void dfs(int u,int fa) {
        st[0][++tot]=u,pos[u]=tot;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w; if (v==fa) continue;
            dep[v]=dep[u]+1,dis[v]=dis[u]+w;
            dfs(v,u),st[0][++tot]=u;
        }
    }
    inline int cmp(int a,int b) { return dep[a]<dep[b]?a:b; }
    inline void init_rmq() {
        for (re int i=2;i<=tot;++i) lg[i]=lg[i>>1]+1;
        for (re int i=1;i<=18;++i)
            for (re int j=1;j+(1<<i)-1<=tot;++j)
                st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    }
    inline int getdis(int u,int v) {
        if (pos[u]>pos[v]) swap(u,v);
        int t=lg[pos[v]-pos[u]+1];
        int lca=cmp(st[t][pos[u]],st[t][pos[v]-(1<<t)+1]);
        return dis[u]+dis[v]-(dis[lca]<<1);
    }
    inline void init() { dfs(1,0); init_rmq(); }
}

namespace T {
    int sz[N],vis[N],fa[N];
    int sumsz,minsz,root;
    inline void getroot(int u,int pa) {
        sz[u]=1; int now=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==pa||vis[v]) continue;
            getroot(v,u),sz[u]+=sz[v];
            now=max(now,sz[v]);
        }
        now=max(now,sumsz-sz[u]);
        if (now<minsz) root=u,minsz=now;
    }
    inline void dfs(int u,int pa,int anc) {
        A[anc].push(OT::getdis(u,fa[anc]));
        for (re int i=head[u];i;i=e[i].nxt)
            if (e[i].v!=pa&&!vis[e[i].v]) dfs(e[i].v,u,anc);
    }
    inline void solve(int u,int pa) {
        vis[u]=1,fa[u]=pa;
        dfs(u,0,u),B[u].push(0),B[pa].push(A[u].top());
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==pa||vis[v]) continue;
            minsz=n,sumsz=sz[v]; getroot(v,u);
            solve(root,u);
        }
        push(B[u]);
    }
    inline void build() {
        root=0,minsz=sumsz=n;
        getroot(1,0); solve(root,0);
    }

    int col[N];
    inline void whiten(int u) {
        del(B[u]),B[u].push(0),push(B[u]);
        for (re int i=u;fa[i];i=fa[i]) {
            del(B[fa[i]]);
            if (A[i].size()) B[fa[i]].del(A[i].top());
            A[i].push(OT::getdis(u,fa[i]));
            B[fa[i]].push(A[i].top());
            push(B[fa[i]]);
        }
    }
    inline void blacken(int u) {
        del(B[u]),B[u].del(0),push(B[u]);
        for (re int i=u;fa[i];i=fa[i]) {
            del(B[fa[i]]);
            if (A[i].size()) B[fa[i]].del(A[i].top());
            A[i].del(OT::getdis(u,fa[i]));
            if (A[i].size()) B[fa[i]].push(A[i].top());
            push(B[fa[i]]);
        }
    }
    inline void query() {
        int Q=read(),num=n;
        while (Q--) {
            char op[2]; scanf("%s",op);
            if (op[0]=='A') {
                if (!num) puts("They have disappeared.");
                else if (num==1) puts("0");
                else printf("%d\n",max(0,ans.top()));
            } else {
                int u=read();
                if (col[u]) whiten(u),col[u]=0,++num;
                else blacken(u),col[u]=1,--num;
            }
        }
    }
}

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    OT::init(); T::build(); T::query();
    return 0;
}

QTREE5

显然可以动态点分治，但是这东西我再也不想写了...

考虑一个 LCT 做法。

每个节点维护一个 $lm$ 和 $rm$ ，分别表示该节点所在的 Splay 中最浅的/最深的节点能到的子树中最近的白点的距离。

考虑这个东西怎么维护。因为 $lm$ 和 $rm$ 类似，这里只考虑 $lm$ 。

显然 $lm_u$ 是以下两部分的最小值：

左子树的答案。
左子树的 $size$ + 右子树的答案 +1。

如果 $u$ 是白点的话，还要加上一部分：左子树的 $size$ 。

考虑怎么算右子树的答案。对每个节点维护一个 multiset ，维护所有虚子树的答案即可。

这个东西在 access 的时候顺便维护一下就好了。

查询就直接 makeroot ，然后查 $lm$ 就好了。

注意 makeroot 时需要 reverse ，而 reverse 时要把 $lm$ 和 $rm$ 也交换！

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,col[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

struct Link_Cut_Tree {
    int fa[N],ch[N][2],sz[N],rev[N];
    int lm[N],rm[N];
    multiset<int> S[N];
    int sta[N];
    inline int fir(int x) { return S[x].empty()?1e9:*(S[x].begin()); }
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void reverse(int x) {
        swap(ch[x][0],ch[x][1]),swap(lm[x],rm[x]),rev[x]^=1;
    }
    inline void pushup(int x) {
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
        lm[x]=min(lm[ch[x][0]],sz[ch[x][0]]+min(fir(x),lm[ch[x][1]]+1));
        if (col[x]) lm[x]=min(lm[x],sz[ch[x][0]]);
        rm[x]=min(rm[ch[x][1]],sz[ch[x][1]]+min(fir(x),rm[ch[x][0]]+1));
        if (col[x]) rm[x]=min(rm[x],sz[ch[x][1]]);
    }
    inline void pushdown(int x) {
        if (rev[x]) {
            if (ch[x][0]) reverse(ch[x][0]);
            if (ch[x][1]) reverse(ch[x][1]);
            rev[x]=0;
        }
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        int y=x,z=0; sta[++z]=y;
        while (nroot(y)) sta[++z]=y=fa[y];
        while (z) pushdown(sta[z--]);
        while (nroot(x)) {
            y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x]) {
            splay(x);
            S[x].insert(lm[ch[x][1]]+1);
            ch[x][1]=y;
            auto it=S[x].lower_bound(lm[ch[x][1]]+1);
            if (it!=S[x].end()&&*it==lm[ch[x][1]]+1) S[x].erase(it);
            pushup(x);
        }
    }
    inline void makeroot(int x) { access(x),splay(x),reverse(x); }
} T;

inline void dfs(int u,int f) {
    T.fa[u]=f;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        T.S[u].insert(1e9),T.pushup(u);
        dfs(v,u);
    }
}

int main() {
    T.lm[0]=T.rm[0]=1e9;
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0);
    Q=read();
    while (Q--) {
        int op=read(),u=read();
        if (!op) {
            T.makeroot(u);
            col[u]^=1,T.pushup(u);
        } else {
            T.makeroot(u);
            printf("%d\n",T.lm[u]>n?-1:T.lm[u]);
        }
    }
    return 0;
}

QTREE6

维护两个 LCT ，一棵维护白点，一棵维护黑点。每次修改暴力 cut 再 link 即可。

然而这样子会被菊花图卡爆。

考虑一种~~我不会~~的套路：把 $u$ 的颜色作为 $(u,fa_u)$ 边的颜色。

同样维护两个 LCT ，一棵维护白边，一棵维护黑边。

可以发现每次修改只需要在一棵树中 cut 掉父边，再在另一棵树中 link 父边即可。

查询就直接 findroot ，然后输出重儿子的大小即可。子树大小按照维护子树信息那一套维护。

一个要注意的地方：这棵树被我们强制成了有根树，所以不能 makeroot 。

另一个要注意的地方：根节点要建一个虚点当它的父节点，这样子根节点才会有父边。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,c[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

struct Link_Cut_Tree {
    int fa[N],ch[N][2],s[N],si[N];
    inline void init() { for (re int i=1;i<=n+1;++i) s[i]=1; }
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void pushup(int x) { s[x]=s[ch[x][0]]+s[ch[x][1]]+si[x]+1; }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        while (nroot(x)) {
            int y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x])
            splay(x),si[x]+=s[ch[x][1]],si[x]-=s[ch[x][1]=y];
    }
    inline int findroot(int x) {
        access(x),splay(x);
        while (ch[x][0]) x=ch[x][0];
        splay(x); return x;
    }
    inline void link(int x,int y) {
        splay(x),access(y),splay(y);
        fa[x]=y,si[y]+=s[x],s[y]+=s[x];
    }
    inline void cut(int x,int y) {
        access(x),splay(x);
        ch[x][0]=fa[ch[x][0]]=0;
        pushup(x);
    }
} T[2];

int fa[N];
inline void dfs(int u,int f) {
    fa[u]=f,T[0].link(u,f);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=f) dfs(e[i].v,u);
}

int main() {
    n=read(); T[0].init(),T[1].init();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,n+1);
    Q=read();
    while (Q--) {
        int op=read(),u=read();
        if (op) T[c[u]].cut(u,fa[u]),c[u]^=1,T[c[u]].link(u,fa[u]);
        else {
            int rt=T[c[u]].findroot(u);
            printf("%d\n",T[c[u]].s[T[c[u]].ch[rt][1]]);
        }
    }
    return 0;
}

QTREE7

和 QTREE6 差不多，每个节点开一个 multiset 维护虚儿子的最大值即可。

然后 link 的时候连虚边有点麻烦，可以直接连实边。

SPOJ AC代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q;
int c[N],w[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

struct Link_Cut_Tree {
    int fa[N],ch[N][2],mx[N]; multiset<int> S[N];
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void pushup(int x) {
        mx[x]=max(w[x],max(mx[ch[x][0]],mx[ch[x][1]]));
        if (S[x].size()) mx[x]=max(mx[x],*S[x].rbegin());
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        while (nroot(x)) {
            int y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x]) {
            splay(x);
            if (ch[x][1]) S[x].insert(mx[ch[x][1]]);
            ch[x][1]=y;
            if (ch[x][1]) S[x].erase(mx[ch[x][1]]);
            pushup(x);
        }
    }
    inline int findroot(int x) {
        access(x),splay(x);
        while (ch[x][0]) x=ch[x][0];
        splay(x); return x;
    }
    inline void link(int x,int y) {
        splay(x),access(y),splay(y);
        fa[x]=y,ch[y][1]=x,pushup(y);
    }
    inline void cut(int x,int y) {
        access(x),splay(x);
        ch[x][0]=fa[ch[x][0]]=0;
        pushup(x);
    }
} T[2];

int fa[N];
inline void dfs(int u,int f) {
    fa[u]=f,T[c[u]].link(u,f);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=f) dfs(e[i].v,u);
}

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    for (re int i=1;i<=n;++i) c[i]=read();
    for (re int i=1;i<=n;++i) w[i]=read();
    T[0].mx[0]=T[1].mx[0]=-2e9; dfs(1,n+1);
    Q=read();
    while (Q--) {
        int op=read(),u=read();
        if (op==0) {
            int rt=T[c[u]].findroot(u);
            printf("%d\n",T[c[u]].mx[T[c[u]].ch[rt][1]]);
        } else if (op==1) {
            T[c[u]].cut(u,fa[u]),c[u]^=1,T[c[u]].link(u,fa[u]);
        } else {
            T[c[u]].access(u),T[c[u]].splay(u);
            w[u]=read(); T[c[u]].pushup(u);
        }
    }
    return 0;
}

SPOJ QTREE 系列简要题解

QTREE1

QTREE2

QTREE3

QTREE4

QTREE5

QTREE6

QTREE7

发表评论取消回复

4 条评论

洛谷5176 公约数

HNOI2019 ～Zero～

APIO2020 ～Intermezzo～

～After OI～

CSP2019 ～Idle Dream～

CF464E The Classic Problem

洛谷4049 [JSOI2007]合金

LOJ2865 「IOI2018」狼人

洛谷3700 [CQOI2017]小Q的表格

洛谷2178 [NOI2015]品酒大会

SPOJ QTREE 系列简要题解

QTREE1

QTREE2

QTREE3

QTREE4

QTREE5

QTREE6

QTREE7

QTREE1

QTREE2

QTREE3

QTREE4

QTREE5

QTREE6

QTREE7

发表评论 取消回复

4 条评论

SPOJ QTREE 系列简要题解

QTREE1

QTREE2

QTREE3

QTREE4

QTREE5

QTREE6

QTREE7

发表评论取消回复