Luogu

分析

首先吐槽一句...当初写《幻想乡战略游戏》的时候抄了个错的 ST 表求 LCA 的板子,那题竟然还过了...

然后我蒯过来出现各种问题,害我调了好久 QAQ


看到这个毒瘤的时限以及修改操作可以想到动态点分治。

对于每个节点 $u$ 维护两个堆:一个堆维护点分子树中所有关灯的点到 $u$ 在点分树上父亲的距离,一个维护所有儿子的前一个堆的堆顶。这样子就很好计算每个点的答案了。

再维护一个堆,维护每个节点最长链与次长链的和。

然后每次查询就是最后那个堆的最大值,修改就直接在点分树上暴跳父节点,然后修改堆中的值即可。

代码细节挺多的...写起来比较想死

代码

将近 5KB 的超长代码,但是结构应该比较清楚

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#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,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 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],tot=0;
    inline void dfs(int u,int fa) {
        st[0][++tot]=u,pos[u]=tot,dep[u]=dep[fa]+1;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==fa) continue;
            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 dep[u]+dep[v]-(dep[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 turnoff(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 turnon(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]=='G') {
                if (!num) puts("-1");
                else if (num==1) puts("0");
                else printf("%d\n",max(0,ans.top()));
            } else {
                int u=read();
                if (col[u]) turnoff(u),col[u]=0,++num;
                else turnon(u),col[u]=1,--num;
            }
        }
    }
}

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    OT::init(); T::build(); T::query();
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 29 PM