自动搬运

查看原文

来自洛谷，原作者为

	zzzyyyyhhhhh omori will become sunny

搬运于2025-08-24 22:26:04，当前版本为作者最后更新于2024-12-12 07:38:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

因为每个连通块最多删一条边，所以第二问可以转化为在每个连通块内选一个深度最大的节点使所有此连通块内的关键点都是它的子孙，这条边就是这个点与父亲相连的边。所有关键点的 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';
}