Codeforces 258E - Little Elephant and Tree（根号暴力/线段树+标记永久化/主席树+标记永久化/普通线段树/可撤销线段树，hot tea）

Codeforces 题目传送门 & 洛谷题目传送门

yyq：“hot tea 不常有，做过了就不能再错过了”

似乎这是半年前某场 hb 模拟赛的 T2？当时 ycx、ymx、yxh 都去打了，可我似乎那时候还在旅游？

不难发现，对于操作 \(i\) 实际上是将 \(a_i\) 与 \(b_i\) 子树的并集内的点的答案集合并上 \(a_i\) 与 \(b_i\) 子树的并集。于是我们考虑将询问离线下来并在树上进行一遍 DFS，动态地维护一个可重集 \(S\)。当我们第一次访问某个点 \(x\) 的时候就遍历所有 \(a_i=x\lor b_i=x\) 的操作 \(i\)，并将 \(subtree(a_i)\cup subtree(b_i)\) 中所有点加入 \(S\)，那么显然此时 \(S\) 中所有点都与 \(x\) 有相同的数，也就是说，如果 \(|S|=0\) 那么 \(ans_x=0\)，否则 \(ans_x=|S|-1\)（要扣掉 \(x\) 本身），这个很好想通。回溯的时候就撤销全部在 \(x\) 处加入 \(S\) 的点即可。

我们不妨用 DFS 序的角度考虑这个问题。显然子树对应的 DFS 序是一段连续的区间 \([L_x,R_x]\)。而一个点 \(x\) 在 \(S\) 中出现的次数也可量化为 \(cnt_x\)，故上述 DFS 的过程可翻译为以下三种操作：

• 将一个点 \(x\) 子树内所有点加入可重集，i.e. \(\forall u\in[bg_x,ed_x],cnt_u\leftarrow cnt_u+1\)。
• 将一个点 \(x\) 子树内所有点从可重集中删除，i.e. \(\forall u\in[bg_x,ed_x],cnt_u\leftarrow cnt_u-1\)。
• 求可重集中有多少个不同的点，i.e. \(\sum\limits_{u=0}^n[cnt_u>0]\)

于是现在我们的任务就是怎样解决这个子问题。针对这个子问题给出了五种解法：

解法一：根号暴力。

u1s1 根号暴力 ta 不香吗？

考虑将整个序列每 \(B\) 个划分为一块。对于每一块我们开一个桶 \(buc_{i,j}\) 表示第 \(i\) 块中有多少个 \(u\) 满足 \(cnt_u=j\)，当我们对某个区间进行整体 \(+v\) 的时候，我们就套路地采用边角块暴力，中间块打标记的方式，也就是边角块暴力地对 \(cnt_u,buc_u\) 进行修改，中间块维护一个 \(tag_i\) 并令 \(tag_i\leftarrow tag_i+v\)。查询时我们可拿总数 \(n\) 减去 \(cnt_i=0\) 的个数，这个又可以通过 \(\sum\limits cnt_{i,-tag_i}\) 求出。

时间复杂度 \(\dfrac{n^2}{B}+nB\)，空间复杂度 \(\dfrac{n^2}{B}\)，显然 \(B=\sqrt{n}\) 时候最优。

ycx 神仙说此题桶要开 short，可似乎开 int 也能过？

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
	#define FILE_SIZE 1<<23
	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
	inline void putc(char x){(*p3++=x);}
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=1e5;
const int SQRT=316;
int n,m,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
vector<int> qv[MAXN+5];int bgt[MAXN+5],edt[MAXN+5],tim=0;
int blk,blk_cnt,L[SQRT+5],R[SQRT+5],bel[MAXN+5];
int val[MAXN+5],tag[SQRT+5];short cnt[SQRT+5][MAXN+5];
void dfs0(int x=1,int f=0){
	bgt[x]=++tim;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		dfs0(y,x);
	} edt[x]=tim;
}
void add(int l,int r,int v){
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) cnt[bel[l]][val[i]]--;
		for(int i=l;i<=r;i++) val[i]+=v;
		for(int i=l;i<=r;i++) cnt[bel[l]][val[i]]++;
	} else {
		for(int i=l;i<=R[bel[l]];i++) cnt[bel[l]][val[i]]--;
		for(int i=l;i<=R[bel[l]];i++) val[i]+=v;
		for(int i=l;i<=R[bel[l]];i++) cnt[bel[l]][val[i]]++;
		for(int i=L[bel[r]];i<=r;i++) cnt[bel[r]][val[i]]--;
		for(int i=L[bel[r]];i<=r;i++) val[i]+=v;
		for(int i=L[bel[r]];i<=r;i++) cnt[bel[r]][val[i]]++;
		for(int i=bel[l]+1;i<=bel[r]-1;i++) tag[i]+=v;
	}
}
int query(){
	int ret=0;
	for(int i=1;i<=blk_cnt;i++) ret+=cnt[i][-tag[i]];
	return n-ret;
}
int ans[MAXN+5];
void calc(int x=1,int f=0){
	for(int i=0;i<qv[x].size();i++){
		int y=qv[x][i];
		add(bgt[x],edt[x],1);
		add(bgt[y],edt[y],1);
	} ans[x]=query();
	if(ans[x]) ans[x]--;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		calc(y,x);
	}
	for(int i=0;i<qv[x].size();i++){
		int y=qv[x][i];
		add(bgt[x],edt[x],-1);
		add(bgt[y],edt[y],-1);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),qv[u].pb(v),qv[v].pb(u);
	blk=(int)pow(n,0.5);blk_cnt=(n-1)/blk+1;
	for(int i=1;i<=blk_cnt;i++){
		L[i]=(i-1)*blk+1;R[i]=min(i*blk,n);
		for(int j=L[i];j<=R[i];j++) bel[j]=i;
		cnt[i][0]=R[i]-L[i]+1;
	} dfs0();calc();
	for(int i=1;i<=n;i++) printf("%d%c",ans[i],(i==n)?'\n':' ');
	return 0;
}

解法二：线段树+标记永久化

u1s1 在做此题之前我还不知道啥是标记永久化，感谢这题让我学会了一个新算法

在上面的根号暴力中，我们没有用到此题一个很重要的性质，那就是我们肯定是先加入再撤销贡献的，也就是说任何时刻都有 \(\forall u,cnt_u\ge 0\)。

于是我们考虑这样一个思路，用线段树维护上面的操作。当我们执行线段树区间修改的时候，我们标记照样打，不过我们不下放标记（这是标记永久化与普通线段树的区别所在）。显然根据之前的推论任意时刻任意节点的标记都非负。线段树上每个节点维护一个值 \(val\) 表示该节点表示的区间中有多少个 \(cnt_u=0\)，而如果我们发现某个区间的标记非负，就意味着该区间中所有 \(cnt_u\) 都 \(>0\)，直接 \(val_i=0\) 即可。否则 \(val_i\) 就是其左右儿子 \(val\) 之和。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
	#define FILE_SIZE 1<<23
	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
	inline void putc(char x){(*p3++=x);}
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=1e5;
const int SQRT=316;
int n,m,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
vector<int> qv[MAXN+5];int bgt[MAXN+5],edt[MAXN+5],tim=0;
struct node{int l,r,val,lz;} s[MAXN*4+5];
void pushup(int k){
	if(s[k].l==s[k].r) s[k].val=!s[k].lz;
	else s[k].val=(s[k].lz)?0:(s[k<<1].val+s[k<<1|1].val);
}
void build(int k,int l,int r){
	s[k].l=l;s[k].r=r;if(l==r){pushup(k);return;}int mid=l+r>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);
}
void modify(int k,int l,int r,int x){
	if(l<=s[k].l&&s[k].r<=r){s[k].lz+=x;pushup(k);return;}
	int mid=s[k].l+s[k].r>>1;
	if(r<=mid) modify(k<<1,l,r,x);
	else if(l>mid) modify(k<<1|1,l,r,x);
	else modify(k<<1,l,mid,x),modify(k<<1|1,mid+1,r,x);
	pushup(k);
}
void dfs0(int x=1,int f=0){
	bgt[x]=++tim;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		dfs0(y,x);
	} edt[x]=tim;
}
int ans[MAXN+5];
void calc(int x=1,int f=0){
	for(int i=0;i<qv[x].size();i++){
		int y=qv[x][i];
		modify(1,bgt[x],edt[x],1);
		modify(1,bgt[y],edt[y],1);
	} ans[x]=n-s[1].val;
	if(ans[x]) ans[x]--;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		calc(y,x);
	}
	for(int i=0;i<qv[x].size();i++){
		int y=qv[x][i];
		modify(1,bgt[x],edt[x],-1);
		modify(1,bgt[y],edt[y],-1);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),qv[u].pb(v),qv[v].pb(u);
	dfs0();build(1,1,n);calc();
	for(int i=1;i<=n;i++) printf("%d%c",ans[i],(i==n)?'\n':' ');
	return 0;
}

解法三：主席树+标记永久化

qwq 事实上与解法二本质上相同？

大概就是区间赋 \(1\)，求全局 \(0\) 的个数，回到历史版本，这个显然主席树可以实现。

然鹅这是蒟蒻第一次打带区间修改的主席树哦

貌似这题空间卡得蛮紧的

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
	#define FILE_SIZE 1<<23
	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
	inline void putc(char x){(*p3++=x);}
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=1e5;
const int SQRT=316;
int n,m,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
vector<int> qv[MAXN+5];int bgt[MAXN+5],edt[MAXN+5],tim=0;
struct node{int val,lz,ch[2];} s[MAXN*120+5];
void pushup(int k,int l,int r){
	if(l==r) s[k].val=!s[k].lz;
	else s[k].val=(s[k].lz)?0:(s[s[k].ch[0]].val+s[s[k].ch[1]].val);
}
int pre,ncnt=0;
void build(int &k,int l,int r){
	k=++ncnt;if(l==r){pushup(k,l,r);return;}int mid=l+r>>1;
	build(s[k].ch[0],l,mid);build(s[k].ch[1],mid+1,r);pushup(k,l,r);
}
int modify(int k,int ql,int qr,int l,int r,int x){
	int id=++ncnt;s[id]=s[k];
	if(ql<=l&&r<=qr){s[id].lz+=x;pushup(id,l,r);return id;}
	int mid=l+r>>1;
	if(qr<=mid) s[id].ch[0]=modify(s[k].ch[0],ql,qr,l,mid,x);
	else if(ql>mid) s[id].ch[1]=modify(s[k].ch[1],ql,qr,mid+1,r,x);
	else{
		s[id].ch[0]=modify(s[k].ch[0],ql,mid,l,mid,x);
		s[id].ch[1]=modify(s[k].ch[1],mid+1,qr,mid+1,r,x);
	} pushup(id,l,r);return id;
}
void dfs0(int x=1,int f=0){
	bgt[x]=++tim;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		dfs0(y,x);
	} edt[x]=tim;
}
int ans[MAXN+5];
void calc(int x=1,int f=0){
	int tmp=pre;
	for(int i=0;i<qv[x].size();i++){
		int y=qv[x][i];
		pre=modify(pre,bgt[x],edt[x],1,n,1);
		pre=modify(pre,bgt[y],edt[y],1,n,1);
	} ans[x]=n-s[pre].val;
	if(ans[x]) ans[x]--;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		calc(y,x);
	} pre=tmp;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),qv[u].pb(v),qv[v].pb(u);
	dfs0();build(pre,1,n);calc();
	for(int i=1;i<=n;i++) printf("%d%c",ans[i],(i==n)?'\n':' ');
	return 0;
}

解法四：线段树

这是我的解法，似乎 rng 神仙也是这个解法？

还是利用“\(0\) 是所有 \(cnt_u\) 的最小可到达的值”这个性质。我们知道 \(cnt_u=0\) 的个数不太好维护，那么我们怎样将其转化为可维护的东西呢？

考虑借鉴 CF997E 的套路，\(cnt_u=0\) 的个数不太好维护，可是区间最小值的个数非常好维护！也就是说，我们每个区间维护区间最小值的个数，查询的时候，如果全局最小值 \(>0\) 就说明不存在 \(cnt_u=0\)，否则直接返回全局最小值的个数即可。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
	#define FILE_SIZE 1<<23
	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
	inline void putc(char x){(*p3++=x);}
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=1e5;
int n,m,ans[MAXN+5];vector<int> qv[MAXN+5];
int hd[MAXN+5],nxt[MAXN*2+5],to[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int bgt[MAXN+5],edt[MAXN+5],tim=0;
void dfs(int x,int f){
	bgt[x]=++tim;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		dfs(y,x);
	} edt[x]=tim;
}
struct node{int l,r,mn,mnc,lz;} s[MAXN*4+5];
void pushup(int k){
	s[k].mn=min(s[k<<1].mn,s[k<<1|1].mn);
	s[k].mnc=0;
	if(s[k].mn==s[k<<1].mn) s[k].mnc+=s[k<<1].mnc;
	if(s[k].mn==s[k<<1|1].mn) s[k].mnc+=s[k<<1|1].mnc;
}
void build(int k,int l,int r){
	s[k].l=l;s[k].r=r;s[k].mnc=r-l+1;if(l==r) return;
	int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void pushdown(int k){
	if(s[k].lz){
		s[k<<1].mn+=s[k].lz;s[k<<1].lz+=s[k].lz;
		s[k<<1|1].mn+=s[k].lz;s[k<<1|1].lz+=s[k].lz;
		s[k].lz=0;
	}
}
void modify(int k,int l,int r,int x){
	if(l<=s[k].l&&s[k].r<=r){
		s[k].mn+=x;s[k].lz+=x;return;
	} pushdown(k);int mid=s[k].l+s[k].r>>1;
	if(r<=mid) modify(k<<1,l,r,x);
	else if(l>mid) modify(k<<1|1,l,r,x);
	else modify(k<<1,l,mid,x),modify(k<<1|1,mid+1,r,x);
	pushup(k);
}
void calc(int x,int f){
	for(int i=0;i<qv[x].size();i++){
		int y=qv[x][i];
		modify(1,bgt[x],edt[x],1);
		modify(1,bgt[y],edt[y],1);
	} if(s[1].mn>0) ans[x]=n;
	else ans[x]=n-s[1].mnc;
	if(ans[x]) ans[x]--;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		calc(y,x);
	}
	for(int i=0;i<qv[x].size();i++){
		int y=qv[x][i];
		modify(1,bgt[x],edt[x],-1);
		modify(1,bgt[y],edt[y],-1);
	}
}
int main(){
	scanf("%d%d",&n,&m);build(1,1,n);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);dfs(1,0);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),qv[u].pb(v),qv[v].pb(u);calc(1,0);
	for(int i=1;i<=n;i++) printf("%d%c",ans[i],(i==n)?'\n':' ');
	return 0;
}

解法五：可撤销线段树

这是 ycx 发明出来的解法，ycx 带发明家！

不难发现这个撤销操作具有时效性，也就是说，我们访问完 \(x\) 子树内所有节点之后，下一步即将撤销的操作就是 \(x\) 加入的操作，故我们可以借鉴线段树分治的思想，用个栈记录这一步的修改的节点编号以及它们原来的值，回溯的时候就按照线段树分治的套路撤销即可。

时空复杂度均为 \(n\log n\)，貌似这个解法是同时卡着时限和空限过去的？（3960ms/4000ms，225400KB/262144KB）

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
	#define FILE_SIZE 1<<23
	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
	inline void putc(char x){(*p3++=x);}
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=1e5;
int n,m,ans[MAXN+5];vector<int> qv[MAXN+5];
int hd[MAXN+5],nxt[MAXN*2+5],to[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int bgt[MAXN+5],edt[MAXN+5],tim=0;
void dfs(int x,int f){
	bgt[x]=++tim;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		dfs(y,x);
	} edt[x]=tim;
}
struct node{int val,lz;} s[MAXN*4+5];
stack<stack<pair<int,node> > > stk;
void pushup(int k){
	stk.top().push(mp(k,s[k]));
	s[k].val=s[k<<1].val+s[k<<1|1].val;
}
void build(int k,int l,int r){
	if(k==1) stk.push(stack<pair<int,node> >());
	s[k].val=r-l+1;if(l==r) return;
	int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
	pushup(k);
}
void tag(int k){stk.top().push(mp(k,s[k]));s[k].val=0;s[k].lz=1;}
void pushdown(int k){
	stk.top().push(mp(k,s[k]));
	if(s[k].lz) tag(k<<1),tag(k<<1|1),s[k].lz=0;
}
void modify(int k,int ql,int qr,int l,int r){
	if(k==1) stk.push(stack<pair<int,node> >());
	if(ql<=l&&r<=qr){tag(k);return;}
	pushdown(k);int mid=l+r>>1;
	if(qr<=mid) modify(k<<1,ql,qr,l,mid);
	else if(ql>mid) modify(k<<1|1,ql,qr,mid+1,r);
	else modify(k<<1,ql,mid,l,mid),modify(k<<1|1,mid+1,qr,mid+1,r);
	pushup(k);
}
void cancel(){
	stack<pair<int,node> > tmp=stk.top();stk.pop();
	while(!tmp.empty()) s[tmp.top().fi]=tmp.top().se,tmp.pop();
}
void calc(int x,int f){
	int tmp=stk.size();
	for(int i=0;i<qv[x].size();i++){
		int y=qv[x][i];
		modify(1,bgt[x],edt[x],1,n);
		modify(1,bgt[y],edt[y],1,n);
	} ans[x]=n-s[1].val;
	if(ans[x]) ans[x]--;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		calc(y,x);
	}
	while(stk.size()>tmp) cancel();
}
int main(){
	scanf("%d%d",&n,&m);build(1,1,n);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);dfs(1,0);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),qv[u].pb(v),qv[v].pb(u);calc(1,0);
	for(int i=1;i<=n;i++) printf("%d%c",ans[i],(i==n)?'\n':' ');
	return 0;
}

综上，此题确实是一道不错的锻炼数据结构能力的 hot tea。