题解：P7037 [NWRRC2016] Gangsters in Central City

· · 题解

看到有加边和删边，想到线段树分治。发现第一问的答案一定不会超过根节点的度数（删掉根节点的所有边一定符合条件），因此把根节点删掉，分成几个连通块统计。

第一问比较好做，线段树分治维护有几个连通块内有关键点就可以了。

因为每个连通块最多删一条边，所以第二问可以转化为在每个连通块内选一个深度最大的节点使所有此连通块内的关键点都是它的子孙，这条边就是这个点与父亲相连的边。所有关键点的 lca 满足这个条件，所以维护关键点的 lca 即可，预处理这个点是几个叶子节点的祖先即可。

当然，如果你知道树上多个点的 lca 就是 dfs 序最大的点与 dfs 序最小的点的 lca 这个结论的话可以直接线段树维护第二问，数组记录第一问答案。

代码。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
#define int long long
int n,m;
vector<int> a[N];
vector<int> ad[N*4],r;
int lc[22][N];
int lg,f[22][N],dep[N];
int siz[N],ls[N];
int ans[N],now[22],k[N];
inline void dfs(int x,int fa)
{
    f[0][x]=fa;
    if(a[x].empty())siz[x]=1;
    for(auto i:a[x])dep[i]=dep[x]+1,dfs(i,x),siz[x]+=siz[i];
}
inline int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=lg;~i;i--)if(dep[f[i][x]]>=dep[y])x=f[i][x];
    if(x==y)return x;
    for(int i=lg;~i;i--)if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
    return f[0][x];
}
#define mid ((l+r)>>1)
#define ll (x<<1)
#define rr (x<<1|1)
inline void add(int l1,int r1,int l,int r,int x,int val)
{
    if(l>=l1&&r<=r1){ad[x].push_back(val);return;}
    if(l1<=mid)add(l1,r1,l,mid,ll,val);
    if(r1>mid)add(l1,r1,mid+1,r,rr,val);
}
int v[N],cnt[N],pp,ans1[N];
inline void get(int l,int r,int x,int dep)
{
    now[dep]=now[dep-1];
    map<int,int> s,s1;
    for(auto i:ad[x])
    {
        now[dep]-=siz[k[f[lg][i]]];
        if(s1.find(f[lg][i])==s1.end())s1[f[lg][i]]=k[f[lg][i]];
        if(k[f[lg][i]])k[f[lg][i]]=lca(k[f[lg][i]],i);
        else k[f[lg][i]]=i;
        now[dep]+=siz[k[f[lg][i]]];
        s[f[lg][i]]=k[f[lg][i]];
        if(!cnt[f[lg][i]])pp++;
        cnt[f[lg][i]]++;
    }
    if(l==r){ans[l]+=now[dep];ans1[l]=pp;for(auto i:s1)k[f[lg][i.first]]=i.second;for(auto i:ad[x]){cnt[f[lg][i]]--;if(!cnt[f[lg][i]])pp--;}return;}
    get(l,mid,ll,dep+1);
    for(auto i:s)
        k[f[lg][i.first]]=i.second;
    get(mid+1,r,rr,dep+1);
    for(auto i:s1)k[f[lg][i.first]]=i.second;
    for(auto i:ad[x]){cnt[f[lg][i]]--;if(!cnt[f[lg][i]])pp--;}
}
#undef mid
#undef rr
#undef ll
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int x;
    for(int i=2;i<=n;i++)cin>>x,a[x].push_back(i);
    for(auto i:a[1])r.push_back(i);
    for(auto i:r)dfs(i,i);
    lg=__lg(n)+1;
    for(int i=1;i<=lg;i++)
        for(int j=1;j<=n;j++)f[i][j]=f[i-1][f[i-1][j]];
    char c;
    int tmp=0;
    for(int i=1;i<=m;i++)
    {
        cin>>c>>x;
        if(c=='+')ls[x]=i,tmp++;
        else
        {
            add(ls[x],i-1,1,m+1,1,x);
            ls[x]=0;
            tmp--;
        }
        ans[i]=-tmp;
    }
    for(int i=1;i<=n;i++)if(ls[i])add(ls[i],m+1,1,m+1,1,i);
    get(1,m+1,1,1);
    for(int i=1;i<=m;i++)
        cout<<ans1[i]<<' '<<ans[i]<<'\n';
}