【loj3329】「WC2020」有根树

2024-03-25 18:21:52

  • 一个性质：\(C\) 一定是 \(S\) 集合中 \(w\) 值最大的若干个点（记作集合 \(A\)）和根形成的连通块。
  • 考虑反证：若 \(\exists x,x\in S\backslash A\)，那 \(x\) 必为 \(A\) 中某个点（设为 \(y\)）的祖先，所以 \(w_x>w_y\)，不满足 \(A\) 的定义。
  • 令 \(B=S-A\)，我们强制钦定 \(|A|\geq\max_{x\in B} w_x\)。每一次询问要求的答案就是当前的 \(|A|\)。
  • 根据定义，显然有：\(\max_{x\in B} w_x\leq \min_{x\in A} w_x\)。记 \(ans=|A|\)。

\(O(n \log^2 n)\) 做法

  • 对原树进行轻重链剖分。
  • 线段树维护每个节点子树内的 \(\max_{x\in B} w_x\)和 \(\min_{x\in A} w_x\)（分别记为 \(mx[now],mn[now]\)），询问时调整。
  • 初始时，\(mx[now]=-INF,mn[now]=INF\)，代表子树中没有在 \(S\) 中的点。
  • 加入一个数 \(x\) 时，先将它加入到 \(B\) 中。那么相当于在将 \(x\) 的 \(mx+=INF\)。若原来的值为 \(-INF+k\)，那么现在的值为 \(k\)（\(k\) 即为 \(x\) 子树在 \(S\) 中的点的个数）。然后将 \(x\) 到根路径上的所有 \(w++\)。
  • 删除一个数 \(x\) 时，若当前位置 \(mx<0\)，说明并不在 \(A\) 中，就从 \(B\) 中删除，\(mx-=INF\)。否则从 \(A\) 中删除，\(mn+=INF\)，同时 \(ans--\)。（\(A\) 的大小减少了 \(1\)）。然后将 \(x\) 到根路径上的所有 \(w--\)。
  • 若 \(\max_{x\in B} w_x> \min_{x\in A} w_x\)，再将 \(B\) 中的最大值移入 \(A\) 中，使得其满足 \(A\) 的定义。
  • 若 \(|A|<\max_{x\in B} w_x\)，再将 \(B\) 中的最大值移入 \(A\) 中。（已强制钦定 \(|A|\geq\max_{x\in B} w_x\)）
  • 若 \(|A|>min_{x\in A} w_x\)，当前答案必大于 \(min_{x\in A} w_x\)，那么将 \(A\) 中的最小值移到 \(B\) 中，答案必定不会变劣。
  • 最后得到的 \(|A|\) 就是答案。
/*********************************************************************
	Problem:「WC2020」有根树
	Author:hydd
	Date:2020/8/13
	Encoding:Simplified Chinese (GB2312)
*********************************************************************/
#include<cstdio>
#include<algorithm>
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
const int INF=0x3f3f3f3f;
char Getchar(){
	static char now[1<<20],*A,*B;
	if (B==A){
		B=(A=now)+fread(now,1,1<<20,stdin);
		if (B==A) return EOF;
	}
	return *A++;
}
int read(){
	int x=0,f=1;
	char ch=Getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=Getchar();
	}
	while (ch<='9'&&ch>='0') x=x*10+ch-'0',ch=Getchar();
	return x*f;
}
int n,q,ans,fa[510000],sz[510000];
int dtime,son[510000],top[510000],dfn[510000];
int edgenum,vet[1100000],val[1100000],Next[1100000],Head[510000];
void addedge(int u,int v){
	vet[++edgenum]=v;
	Next[edgenum]=Head[u];
	Head[u]=edgenum;
}
void dfs(int u,int f){
	fa[u]=f; sz[u]=1; son[u]=0;
	for (int e=Head[u],v;e;e=Next[e]){ v=vet[e];
		if (v==f) continue;
		dfs(v,u); sz[u]+=sz[v];
		if (sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tp){
	top[u]=tp; dfn[u]=++dtime;
	if (son[u]) dfs2(son[u],tp);
	for (int e=Head[u],v;e;e=Next[e]){ v=vet[e];
		if (v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}

//namespace Segment Tree
int mn[2100000],mx[2100000],tag[2100000];
inline void pushup(int now){
	mn[now]=min(mn[now<<1],mn[now<<1|1]);
	mx[now]=max(mx[now<<1],mx[now<<1|1]);
}
inline void add(int now,int v){
	mn[now]+=v; mx[now]+=v;
	tag[now]+=v;
}
inline void pushdown(int now){
	if (tag[now]){
		add(now<<1,tag[now]);
		add(now<<1|1,tag[now]);
		tag[now]=0;
	}
}
void change(int now,int l,int r,int x,int v){
	if (l==r){
		if (v>0) mx[now]+=INF;//B中加入
		else if (mx[now]<0) mn[now]+=INF,ans--;//A中删除
		else mx[now]-=INF;//B中删除
		return;
	}
	pushdown(now);
	int mid=(l+r)>>1;
	if (x<=mid) change(now<<1,l,mid,x,v);
	else change(now<<1|1,mid+1,r,x,v);
	pushup(now);
}
void change(int now,int l,int r,int x,int y,int v){
	if (l==x&&r==y){
		add(now,v);
		return;
	}
	pushdown(now);
	int mid=(l+r)>>1;
	if (y<=mid) change(now<<1,l,mid,x,y,v);
	else if (x>mid) change(now<<1|1,mid+1,r,x,y,v);
	else { change(now<<1,l,mid,x,mid,v); change(now<<1|1,mid+1,r,mid+1,y,v);}
	pushup(now);
}
void BtoA(int now,int l,int r){
	if (l==r){
		ans++;
		mx[now]-=INF; mn[now]-=INF;
		return;
	}
	pushdown(now);
	int mid=(l+r)>>1;
	if (mx[now]==mx[now<<1]) BtoA(now<<1,l,mid);
	else BtoA(now<<1|1,mid+1,r);
	pushup(now);
}
void AtoB(int now,int l,int r){
	if (l==r){
		ans--;
		mx[now]+=INF; mn[now]+=INF;
		return;
	}
	pushdown(now);
	int mid=(l+r)>>1;
	if (mn[now]==mn[now<<1]) AtoB(now<<1,l,mid);
	else AtoB(now<<1|1,mid+1,r);
	pushup(now);
}
int main(){
//	File("tree");
	n=read(); int op,u,v;
	for (int i=1;i<n;i++){
		u=read(); v=read();
		addedge(u,v); addedge(v,u);
	}
	dfs(1,0); dfs2(1,1);
	q=read();
	/*
		答案必定是S中w最大的若干个点
		我们选择的S中w最大的若干个点的子集为A，B=S-A
		满足B中最大值<=A中最小值
	*/
	for (int i=1;i<=4*n+1;i++) mn[i]=INF,mx[i]=-INF;
	while (q--){
		op=read(); v=read(); if (op==2) op=-1;
		change(1,1,n,dfn[v],op);
		for (;v;v=fa[top[v]]) change(1,1,n,dfn[top[v]],dfn[v],op);
		/*if (op==1){
			while (mn[1]<mx[1]) BtoA(1,1,n);//A中最小值<B中最大值
		} else{*/
		while (mn[1]<mx[1]) BtoA(1,1,n);//A中最小值<B中最大值
		//}
		while (ans<mx[1]) BtoA(1,1,n);//钦定|A|>=mx[1]
		while (ans>mn[1]) AtoB(1,1,n);//答案已经比mn[1]大了，把它移到B答案不会变劣
		printf("%d\n",ans);
	}
	return 0;
}

\(O(n\log n)\) 做法

  • 对原树进行轻重链剖分后，维护每条重链上：
    • 重链上的点的个数（记作 \(tot\)）。
    • 最靠下的在 \(A\) 中的点与链顶深度之差 \(+1\)。记作 \(up\)），如果没有，设为 \(0\)。\(up\) 的 \(w\) 值（记作 \(up\_w\)）。
    • 最靠上的在 \(B\) 中的点与链顶深度之差 \(+1\)（记作 \(dw\)），如果没有，设为 \(tot+1\)。\(dw\) 的 \(w\) 值（记作 \(dw\_w\)）。
  • 维护一个 \(cnt=|A|\)，再维护 \(lim\)，要求 \(\min_{x\in A} x>lim,\max_{x\in B}\leq lim\)。

在 \(S\) 中插入点 \(x\)

  • 找到 \(x\) 所在的重链，先更新链上的 \(up\_w/dw\_w\) 都 \(+1\)。
  • 如果现在的 \(dw\_w>lim\)，就可以把它移动到 \(A\) 中（而必定只有一个点会移到 \(A\) 中，因为链上从上到下的 \(w\) 值必定是严格递减的）。（此条件有可能满足只有可能最靠上的在 \(B\) 中的点在 \(x\) 上方）
  • 否则，如果当前最靠上的在 \(B\) 中的点在 \(x\) 下方，那么：
    • 如果 \(w_x\leqslant lim\)，那么显然有 \(t-fa[x]\) 链上所有点都在 \(A\) 中，\(son[x]-\cdots\) 链上所有点都在 \(B\) 中，且当前点可以加入 \(B\)，就可以考虑更新 \(up\)。
    • 如果 \(w_x>lim\)，那么显然有 \(t-fa[x]\) 链上所有点都在 \(A\) 中，\(son[x]-\cdots\) 链上所有点都在 \(B\) 中。且当前点可以加入 \(A\)，就可以考虑更新 \(dw\)。
  • 接下来，就是更新到根路径上的其他重链的 \(up\_w/dw\_w\)，然后看要不要上移分界点即可。
  • 最后，当 \(cnt>lim\)，不断将 \(A\) 中值为 \(lim\) 的点移到 \(B\) 中即可。

在 \(S\) 中删除点 \(x\)

  • 找到 \(x\) 所在的重链，先更新链上的 \(up\_w/dw\_w\) 都 \(-1\)。设 \(d\) 为当前点的深度与链顶深度之差 \(+1\)。
  • 如果现在的 \(d\leqslant up[t]\)，说明它现在在 \(A\) 中，删了之后要将 \(cnt--\)。同时如果 \(d=up[t]\)，说明它是 \(A\) 中深度最大的点，删去之后要重新求深度最大的点。
  • 如果现在的 \(d=dw[t]\)，说明它为 \(B\) 中深度最小的点，删去之后要重新求深度最小的点。（在 \(B\) 中但非深度最小的点删去没有影响）。
  • 然后，若 \(up_w[t]\leq lim\) 且 \(up[t]\neq 0\) （这个点存在），那么就可以把它移动到 \(B\) 中，\(cnt--\)。
  • 接下来，就是更新到根路径上的其他重链的 \(up\_w/dw\_w\)，然后看要不要下移分界点即可。
  • 最后，当 \(cnt<lim\)，不断将 \(B\) 值为 \(lim\) 的点移到 \(A\) 中即可。
/*********************************************************************
	Problem:「WC2020」有根树
	Author:hydd
	Date:2020/8/13-2020/8/14
	Encoding:Simplified Chinese (GB2312)
*********************************************************************/
#include<cstdio>
#include<algorithm>
#include<set>
#define File(x) freopen(x".in","r",stdin);//freopen(x".out","w",stdout)
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=510000;
const int MAXM=1100000;
int n,q;
namespace IO{
	const int LEN=1<<20;
	char Getchar(){
		static char now[LEN],*A,*B;
		if (B==A){
			B=(A=now)+fread(now,1,LEN,stdin);
			if (B==A) return EOF;
		}
		return *A++;
	}
	int read(){
		int x=0,f=1;
		char ch=Getchar();
		while (ch<'0'||ch>'9'){
			if (ch=='-') f=-1;
			ch=Getchar();
		}
		while (ch<='9'&&ch>='0') x=x*10+ch-'0',ch=Getchar();
		return x*f;
	}
	char pbuf[LEN],*pp=pbuf;
	void pc(const char c) {
		if (pp-pbuf==LEN) fwrite(pbuf,1,LEN,stdout),pp=pbuf;
		*pp++=c;
	}
	void write(int x){
		static int sta[35];
		if (x<0){ pc('-'); x=-x;}
		int top=0;
		do{
			sta[top++]=x%10;
			x/=10;
		} while (x);
		while (top) pc(sta[--top]+'0');
	}
	void IOflush(){ fwrite(pbuf,1,pp-pbuf,stdout);}
} using namespace IO;
namespace Graph{
	int edgenum,vet[MAXM],val[MAXM],Next[MAXM],Head[MAXN];
	void addedge(int u,int v){
		vet[++edgenum]=v;
		Next[edgenum]=Head[u];
		Head[u]=edgenum;
	}
} using namespace Graph;
namespace HLD{//Heavy-Light Decompositions
	int fa[MAXN],sz[MAXN],son[MAXN];
	int dtime,L[MAXN],R[MAXN],num[MAXN];
	int tot[MAXN],top[MAXN];
	void dfs(int u,int f){
		fa[u]=f; sz[u]=1; son[u]=0;
		for (int e=Head[u],v;e;e=Next[e]){ v=vet[e];
			if (v==f) continue;
			dfs(v,u); sz[u]+=sz[v];
			if (sz[v]>sz[son[u]]) son[u]=v;
		}
	}
	void dfs2(int u,int tp){
		top[u]=tp; tot[tp]++; num[++dtime]=u;
		L[u]=dtime;
		if (son[u]) dfs2(son[u],tp);
		for (int e=Head[u],v;e;e=Next[e]){ v=vet[e];
			if (v==fa[u]||v==son[u]) continue;
			dfs2(v,v);
		}
		R[u]=dtime;
	}
} using namespace HLD;

namespace BIT{//Binary Index Tree
	int tree[MAXN];
	void add(int x,int y){
		for (;x<=n;x+=x&-x) tree[x]+=y;
	}
	int query(int x){
		int res=0;
		for (;x;x-=x&-x) res+=tree[x];
		return res;
	}
} using namespace BIT;

struct List{//表头为权值，后面接着点的编号
	int pre[MAXM],nxt[MAXM];
	void del(int x){
		if (nxt[x]) pre[nxt[x]]=pre[x];
		if (pre[x]) nxt[pre[x]]=nxt[x];
		pre[x]=x; nxt[x]=x;
	}
	void ins(int v,int x){//在权值v后插入点x
		v+=n+1;
		nxt[x]=nxt[v];
		if (nxt[v]) pre[nxt[v]]=x;
		nxt[v]=x; pre[x]=v;
	}
	int get(int v){ return nxt[v+n+1];}
} Up,Dw;
int up[MAXN],dw[MAXN],up_w[MAXN],dw_w[MAXN];
void update(int x){//更新每条链的分界点的值，存入Up,Dw
	Up.del(x);
	if (up[x]>=1) Up.ins(up_w[x],x);
	Dw.del(x);
	if (dw[x]<=tot[x]) Dw.ins(dw_w[x],x);
}
/*
	up[x]为链上最深度最大的A中的点的深度，up_w[x]为其w值
	dw[x]为链上最深度最小的B中的点的深度，dw_w[x]为其w值
	>lim的点放入A中，<=lim的点放入B中
*/
void update_w(int x,int d,int w){//更新分界点的w值
	if (1<=up[x]&&up[x]<=d) up_w[x]+=w;
	if (dw[x]<=d) dw_w[x]+=w;
}
int get_w(int x){ return query(R[x])-query(L[x]-1);}//获得一个在S中的点的w值
set<int> s[MAXN];
set<int>::iterator it;
int pred(int x,int y){
	it=s[x].lower_bound(y);
	if (it==s[x].begin()) return 0;
	else return *--it;
}
int succ(int x,int y){
	it=s[x].upper_bound(y);
	if (it==s[x].end()) return 0;
	else return *it;
}
void delA(int x){//将链上的深度最大的A从A中删除
	up[x]=pred(x,up[x]);
	up_w[x]=!up[x]?0:get_w(num[L[x]+up[x]-1]);
}
void delB(int x){//将链上的深度最大的B从B中删除
	dw[x]=succ(x,dw[x]);
	dw_w[x]=dw[x]>tot[x]?0:get_w(num[L[x]+dw[x]-1]);
}
void AtoB(int x){//将链上的深度最大的A移到B中
	dw[x]=up[x]; dw_w[x]=up_w[x];
	delA(x);
}
void BtoA(int x){//将链上的深度最小的B移到A中
	up[x]=dw[x]; up_w[x]=dw_w[x];
	delB(x);
}
int cnt,lim;
void ins(int x){
	add(L[x],1);
	int t=top[x],d=L[x]-L[t]+1;//d为以t为根时x的深度（t深度为1）
	s[t].insert(d);
	update_w(t,d,1);//更新链上分界点的w（分界点在t--x的链上）
	if (dw_w[t]>lim){ cnt++; BtoA(t);}//直接上移，因为最多分界点只会移动一步
	else
		if (dw[t]>d){//现在已知dw[t]满足条件且在x之下，看分界点是否能移动
			int s=get_w(x);
			if (s<=lim){ dw[t]=d; dw_w[t]=s;}//原先t--fa[x]链上所有点都在A中，son[x]--*所有点都在B中，且当前点可以加入B
			else {
				cnt++;
				if (d>up[t]){ up[t]=d; up_w[t]=s;}//原先t--fa[x]链上所有点都在A中，son[x]--*所有点都在B中，且当前点可以加入A
			}
		}
	update(t);
	for (int x=fa[t],t=top[x];x;x=fa[t],t=top[x]){
		d=L[x]-L[t]+1;
		update_w(t,d,1);//更新链上分界点的w
		if (dw_w[t]>lim){ cnt++; BtoA(t);}//分界点上移
		update(t);
	}
	//前面的操作会导致cnt增大
	while (cnt>lim){
		int x=Up.get(lim);
		if (!x){ lim++; continue;}//没有权值为lim的A中的点
		cnt--; AtoB(x); update(x);
	}
	//做完后cnt==lim
}
void del(int x){
	add(L[x],-1);
	int t=top[x],d=L[x]-L[t]+1;//d为以t为根时x的深度（t深度为1）
	s[t].erase(d);
	update_w(t,d,-1);//更新链上分界点的w（分界点在t--x的链上）
	if (d<=up[t]) cnt--;//从A中删除，因为x已经不在S中了
	if (d==up[t]) delA(t);//若x为A中深度最大的点，删去后要重新求深度最大的点
	else if (d==dw[t]) delB(t);//若x为B中深度最大的点，删去后要重新求深度最大的点
	if (up[t]>=1&&up_w[t]<=lim){ cnt--; AtoB(t);}//x到根路径所有w--，可能导致分界点下移
	update(t);
	for (int x=fa[t],t=top[x];x;x=fa[t],t=top[x]){
		d=L[x]-L[t]+1;
		update_w(t,d,-1);//更新链上分界点的w
		if (up[t]>=1&&up_w[t]<=lim){ cnt--; AtoB(t);}//分界点下移
		update(t);
	}
	//前面的操作会导致cnt减小
	while (cnt<lim){
		int x=Dw.get(lim);
		if (!x){ lim--; continue;}//没有权值为lim的A中的点
		cnt++; BtoA(x); update(x);
	}
}
int main(){
//	File("tree");
	n=read();
	for (int i=1;i<=(n<<1|1);i++){
		Up.pre[i]=0; Up.nxt[i]=0;
		Dw.pre[i]=0; Dw.nxt[i]=0;
	}
	int t,u,v;
	for (int i=1;i<n;i++){
		u=read(); v=read();
		addedge(u,v); addedge(v,u);
	}
	dfs(1,0); dfs2(1,1);
	for (int i=1;i<=n;i++)
		if (top[i]==i){
			dw[i]=tot[i]+1;//B中深度最小的点是i往下dw[i]深度的点
			s[i].insert(0); s[i].insert(tot[i]+1);
		}
	q=read(); 
	while (q--){
		t=read(); v=read();
		if (t==1) ins(v);
		else del(v);
		write(cnt); pc('\n'); 
	}
	IOflush();
	return 0;
}
/*
5
1 2
1 3
1 4
2 5
6
1 4
1 1
1 2
1 5
2 2
1 3
*/
上一篇：[模板][数学] BSGS


下一篇：「高等数学学习笔记 DAY19」