P9620 解题报告

· · 题解

前言

好玩树剖题，这个东西算是让我眼前一亮了。

广告：『从入门到入土』树链剖分学习笔记。

思路分析

简要题意：

给定有 n 个点的树，最开始所有点都是白点，每次操作给一个点染黑/染白。

操作后，得到所有黑点的导出子树，求使这个导出子树的根的深度变化最少要删掉多少黑点。

特别的，如果删空了也算变化。

如果只求根节点的话显然是一个一眼题。

这个比较简单就不再赘述，直接给出经典结论：

原因也比较显然，有兴趣的读者可以自证。

接着考虑怎么样改变根节点的同时删掉的点最少。

我们考虑其实只有两种可能：

  1. 根节点 x 处分多叉子树，每叉里都有黑点。

    此时我们考虑只保留一叉子树然后把多余的全删了就行了。

    也就是找到总点数 w，含有黑点数最多的子树黑点数 w'，答案即为 w-w'。

  2. 根节点处后只有一叉子树，但是根节点是黑点。

    其实这类情况可以直接合并进 1 里，我们把根节点这个黑点当做是子树外的另一叉即可。

这下就变成了，单点修改权值，查询给定点 x 的儿子的子树最大权值。

如果遍历儿子算子树和这显然复杂度会爆掉，所以我们不要写成单点加，子树查。

把这个转化一下，变成链加，单点查。

也就是对于点 x，我们给 x\rightarrow 1 的路径加上修改的权值，那么查询的时候点 y 对应的权值就是他的子树权值和了。

接着我们要考虑的就是快速查询所有儿子权值最大值的方法。

考虑把这东西也交给线段树维护，但是问题来了：

注意到我们不需要子树 dfn 序连续的性质，只需要保证重链 dfn 序连续即可。

所以我们可以对树剖的第二遍 dfs 略加修改，让轻儿子的 dfn 序也连续。

然后就可以比较方便的实现了，具体可以看代码。

代码

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int N=2e5+10,M=3,INF=0x3f3f3f3f,mod=1e9+7,p=13331;
int n,m,cnt,a[N],t[N<<2],lz[N<<2];vector<int>e[N];char s[N];set<int>st;
namespace Fast_IO
{
    static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
    #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
    inline int read()
    {
        int x(0),t(1);char fc(getchar());
        while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
        while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
        return x*t;
    }
    inline void flush(){fwrite(out,1,length,stdout);length=0;}
    inline void put(char c){if(length==9999999) flush();out[length++]=c;}
    inline void put(string s){for(char c:s) put(c);}
    inline void print(int x)
    {
        if(x<0) put('-'),x=-x;
        if(x>9) print(x/10);
        put(x%10+'0');
    }
    inline bool chk(char c) { return !(c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'||c=='?'); }
    inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
    inline void rd(char s[],int&n)
    {
        s[++n]=getchar();
        while(chk(s[n])) s[n]=getchar();
        while(ck(s[n])) s[++n]=getchar();
        n--;
    }
}
using namespace Fast_IO;
namespace tree_decomposition
{
    int fa[N],son[N],si[N],dep[N];
    int top[N],id[N],dfn[N],mn[N];
    inline void clear(int n)
    {
        memset(son,0,sizeof son);
        for(int i=1;i<=n;i++) e[i].clear();
    }
    inline void add(int u,int v){e[u].emplace_back(v),e[v].emplace_back(u);}
    inline void dfs1(int u,int ff)
    {
        fa[u]=ff,si[u]=1,dep[u]=dep[ff]+1;
        for(auto v:e[u])
        {
            if(v==ff) continue;
            dfs1(v,u);si[u]+=si[v];
            if(si[son[u]]<si[v]) son[u]=v;
        }
    }
    inline void dfs2(int u,int topf)
    {
        top[u]=topf;int f=0;if(son[u]) dfn[son[u]]=++cnt,id[cnt]=son[u],dfs2(son[u],topf);
        for(auto v:e[u]) if(v!=fa[u]&&v!=son[u]) mn[u]=f?mn[u]:cnt+1,f=1,dfn[v]=++cnt,id[cnt]=v;
        for(auto v:e[u]) if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
    inline int LCA(int x,int y)
    {
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            x=fa[top[x]];
        }
        return dep[x]<dep[y]?x:y;
    }
}
using namespace tree_decomposition;
inline void pushson(int p,int w){t[p]+=w;lz[p]+=w;}
inline void pushdown(int p){pushson(ls,lz[p]);pushson(rs,lz[p]);lz[p]=0;}
inline void modify(int p,int l,int r,int s,int e,int w)
{
    if(l>=s&&r<=e) return pushson(p,w);pushdown(p);
    if(mid>=s) modify(ls,l,mid,s,e,w);
    if(mid<e) modify(rs,mid+1,r,s,e,w);
    t[p]=max(t[ls],t[rs]);
}
inline void modify(int x,int w)
{
    while(x)
    {
        int y=dep[x]-dep[top[x]];
        if(x^top[x]) modify(1,1,n,dfn[x]-y+1,dfn[x],w);
        modify(1,1,n,dfn[top[x]],dfn[top[x]],w);
        x=fa[top[x]];
    }
}
inline int query(int p,int l,int r,int s,int e)
{
    if(l>=s&&r<=e) return t[p];pushdown(p);int res=0;
    if(mid>=s) res=query(ls,l,mid,s,e);
    if(mid<e) res=max(res,query(rs,mid+1,r,s,e));
    return res;
}
inline int query(int x)
{
    int res=query(1,1,n,dfn[son[x]],dfn[son[x]]);
    int y=e[x].size()-(bool)son[x]-(x!=1);
    if(y<=0) return res;
    return max(res,query(1,1,n,mn[x],mn[x]+y-1));
}
inline void solve()
{
    n=read(),m=read();for(int i=1,u,v;i<n;i++) u=read(),v=read(),add(u,v);
    dfs1(1,0),dfn[1]=++cnt,id[1]=1,dfs2(1,1);
    for(int i=1,l=0,x;i<=m;i++)
    {
        l=0;rd(s,l);x=read();
        if(s[1]=='W'&&a[x]==1) modify(x,-1),st.erase(dfn[x]),a[x]^=1;
        if(s[1]=='R'&&a[x]==0) modify(x,1),st.insert(dfn[x]),a[x]^=1;
        if(st.empty()){put("0\n");continue;}
        if(st.size()==1){put("1\n");continue;}
        int lca=LCA(id[*st.begin()],id[*(--st.end())]);
        print(st.size()-query(lca));put('\n');
    }
}
signed main()
{
    int T=1;while(T--) solve();
    genshin:;flush();return 0;
}