Luogu

分析

设1为安装了,0为没安装。

那么就是求每次操作前后树的所有节点的权值和的差的绝对值。

对于install,把它到根节点的路径上所有点的权值都修改成1。

对于uninstall,把以它为根的子树内所有点的权值都修改成0。

然后这题就做完了。

线段树需要资瓷区间赋值和区间求和。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#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 MAXN=100000+10;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,q;

int dep[MAXN],sz[MAXN],hson[MAXN],fa[MAXN];
int top[MAXN],id[MAXN],real[MAXN];
int tot=0;

inline void Dfs1(int u,int f) {
    fa[u]=f,sz[u]=1;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==f) continue;
        dep[v]=dep[u]+1;
        Dfs1(v,u);
        sz[u]+=sz[v];
        if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void Dfs2(int u,int anc) {
    top[u]=anc,id[u]=++tot,real[tot]=u;
    if (!hson[u]) return;
    Dfs2(hson[u],anc);
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa[u]&&v!=hson[u]) Dfs2(v,v);
    }
}

struct Segment_Tree {
    int sumv[MAXN<<2],setv[MAXN<<2];
#define lson (o<<1)
#define rson (o<<1|1)
    inline void pushup(int o) { sumv[o]=sumv[lson]+sumv[rson]; }
    inline void pushdown(int o,int l,int r) {
        if (setv[o]!=-1) {
            int mid=(l+r)>>1;
            setv[lson]=setv[rson]=setv[o];
            sumv[lson]=setv[o]*(mid-l+1);
            sumv[rson]=setv[o]*(r-mid);
            setv[o]=-1;
        }
    }
    inline void build(int o,int l,int r) {
        if (l==r) { sumv[o]=0,setv[o]=-1; return; }
        int mid=(l+r)>>1;
        build(lson,l,mid); build(rson,mid+1,r);
        pushup(o);
    }
    inline void update(int o,int l,int r,int ql,int qr,int v) {
        if (ql<=l&&r<=qr) { sumv[o]=v*(r-l+1),setv[o]=v; return; }
        int mid=(l+r)>>1;
        pushdown(o,l,r);
        if (ql<=mid) update(lson,l,mid,ql,qr,v);
        if (qr>mid) update(rson,mid+1,r,ql,qr,v);
        pushup(o);
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return sumv[o];
        int mid=(l+r)>>1,rt=0;
        pushdown(o,l,r);
        if (ql<=mid) rt+=query(lson,l,mid,ql,qr);
        if (qr>mid) rt+=query(rson,mid+1,r,ql,qr);
        pushup(o);
        return rt;
    }
};

Segment_Tree T;
int last=0;

inline void install(int u) {
    int v=1,tu=top[u],tv=top[v];
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) { swap(tu,tv); swap(u,v); }
        T.update(1,1,n,id[tu],id[u],1);
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    T.update(1,1,n,id[v],id[u],1);
    int now=T.query(1,1,n,1,n);
    printf("%d\n",abs(now-last));
    last=now;
}

inline void uninstall(int u) {
    T.update(1,1,n,id[u],id[u]+sz[u]-1,0);
    int now=T.query(1,1,n,1,n);
    printf("%d\n",abs(now-last));
    last=now;
}

char s[110];

int main() {
    n=read();
    for (re int i=2;i<=n;++i) {
        int depend=read()+1;
        addEdge(depend,i);
        addEdge(i,depend);
    }
    dep[1]=1; Dfs1(1,0); Dfs2(1,1); T.build(1,1,n);
    q=read();
    while (q--) {
        char c=getchar(); while (c<'a'||c>'z') c=getchar();
        if (c=='i') install(read()+1);
        else if (c=='u') uninstall(read()+1);
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 31 PM