WA on test #4

#include<bits/stdc++.h>
#define int long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
int n,q,k,pt;
int x,y,cnt,dfn[200005],dep[200005],mx[800005],tag[800005],siz[200005];
vector<int> task_id[200005];
vector<int> task_k[200005];
vector<int> t[200005];
bool vis[200005];int reveal[200005];
inline void _init(int now,int dp){//预处理节点深度，dfs序,子树大小
	//printf("_init(%d,%d);",now,dp);cout<<endl;
	dfn[now]=++cnt;dep[dfn[now]]=dp;vis[now]=1;siz[now]=1;
	for(int i=0;i<t[now].size();i++){
		if(vis[t[now][i]]) continue;
		_init(t[now][i],dp+1);
		siz[now]+=siz[t[now][i]];
	}
	return;
}
inline void update(int rt){
	mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
	return;
}
void build(int l,int r,int rt){
	if(l==r){
		mx[rt]=dep[l];
		//cout<<"["<<l<<','<<r<<"]->"<<mx[rt]<<endl;
		return;
	}
	int mid=(l+r)>>1;
	build(lson);build(rson);
	update(rt);
	//cout<<"["<<l<<','<<r<<"]->"<<mx[rt]<<endl;
	return;
}
inline void color(int l,int r,int rt,int c){
	mx[rt]+=c;
	tag[rt]+=c;
	return;
}
inline void ph_tg(int l,int r,int rt){
	if(tag[rt]==0){
		return;
	}
	int mid=(l+r)>>1;
	color(lson,tag[rt]);
	color(rson,tag[rt]);
	tag[rt]=0;
	return;
}
void modify(int l,int r,int rt,int c){
	if(x<=l&&r<=y){
		color(l,r,rt,c);
		return;
	}
	ph_tg(l,r,rt);
	int mid=(l+r)>>1;
	if(x<=mid) modify(lson,c);
	if(y>mid) modify(rson,c);
	update(rt);
	return;
}
int query(int l,int r,int rt){
	if(x<=l&&r<=y){
		return mx[rt];
	}
	ph_tg(l,r,rt);
	int ans=0,mid=(l+r)>>1;
	if(x<=mid) ans=max(ans,query(lson));
	if(y>mid) ans=max(ans,query(rson));
	//printf("query(%d,%d,%d); ans:%d",l,r,rt,ans);cout<<endl;
	return ans;
}
inline void upd(int now,int pre,int dir){//dir 1表示向下走,2表示回溯
	if(now==pre) return;
	if(dir==1){
		x=1,y=n;modify(1,n,1,1);
		x=dfn[now],y=dfn[now]+siz[now]-1;modify(1,n,1,-2);
		//cout<<pre<<"->"<<now<<' '<<"["<<x<<","<<y<<"];"<<endl;
		//for(int i=1;i<=n*2;i++) cout<<mx[i]<<' ';
		//cout<<endl;
		//for(int i=1;i<=n*2;i++) cout<<tag[i]<<' ';
		//cout<<endl;
	}else{
		x=1,y=n;modify(1,n,1,-1);
		x=dfn[now],y=dfn[now]+siz[now]-1;modify(1,n,1,2);
		//cout<<now<<"->"<<pre<<' '<<"["<<x<<","<<y<<"];"<<endl;
	}
	//cout<<x<<" "<<y<<endl;
	return;
}
inline bool cmp(pair<int,int> a,pair<int,int> b){
	return a.first<b.first;
}
inline void deal(int now,int id){
	vector<pair<int,int> > intervals;//维护不可达的点的dfs序区间
	int rm;
	//printf("deal(%d,%d);",now,id);cout<<endl;
	for(int p=0;p<task_k[id].size();p++){
		rm=task_k[id][p];
		if(dfn[now]>dfn[rm]&&dfn[now]<dfn[rm]+siz[rm]){//要删除的点是now的祖先
			int fa;
			for(int i=0;i<t[rm].size();i++){//这里可以(必须?)优化成二分查找
				if(dfn[t[rm][i]]<=dfn[now]){
					fa=t[rm][i];
				}else{
					break;
				}
			}
			intervals.push_back({1,dfn[fa]-1});
			intervals.push_back({dfn[fa]+siz[fa],n});
			//cout<<"findfa:"<<fa<<endl;
		}else{//否则直接删除rm的子树
			intervals.push_back({dfn[rm],dfn[rm]+siz[rm]-1});
		}
	}
	sort(intervals.begin(),intervals.end(),cmp);
	int avai_l=1,avai_r=0,ans=0;//可用区间左右端点以及答案
	vector<pair<int,int> > together;//存储合并后的区间
	int at=-1;
	for(int i=0;i<intervals.size();i++){//注意这里，可能有锅
		if(at==-1){
			together.push_back(intervals[i]);
			at=0;
		}else if(together[at].second>=intervals[i].first-1){
			together[at].second=max(together[at].second,intervals[i].second);
		}else{
			together.push_back(intervals[i]);
			++at;
		}
	}
	//cout<<"at:"<<at<<endl;
	if(at!=-1){
		for(int i=0;i<=at;i++){
			//cout<<"Uh-huh?"<<endl;
			//cout<<i<<"->i"<<endl;
			if(i==0){
				avai_l=1;avai_r=together[0].first-1;
				if(avai_r>=avai_l){
					x=avai_l;y=avai_r;
					//cout<<"request:"<<"("<<x<<","<<y<<")"<<endl;
					ans=max(ans,query(1,n,1));
				}else{
					//cout<<"tried:"<<avai_l<<'~'<<avai_r<<endl;
				}
			}else{
				avai_l=together[i-1].second+1;
				avai_r=together[i].first-1;
				if(avai_r>=avai_l){
					x=avai_l;y=avai_r;
					//cout<<"request:"<<"("<<x<<","<<y<<")"<<endl;
					ans=max(ans,query(1,n,1));
				}
				else{
					//cout<<"tried:"<<avai_l<<'~'<<avai_r<<endl;
				}
			}
		}
		avai_l=together[at].second+1,avai_r=n;
		if(avai_r>=avai_l){
			x=avai_l,y=avai_r;
			//cout<<"request:"<<"("<<x<<","<<y<<")"<<endl;
			ans=max(ans,query(1,n,1));
		}
		else{
			//cout<<"tried:"<<avai_l<<'~'<<avai_r<<endl;
		}
	}else{
		x=1,y=n;
		ans=max(ans,query(1,n,1));
	}
	//cout<<"Ans:"<<ans<<endl;
	reveal[id]=ans;
	return;
}
void dfs(int now,int pre){//我们离线存储了询问，现在可以按照dfs序解决每个节点
	//cout<<"dfs("<<now<<","<<pre<<");"<<endl;
	upd(now,pre,1);int num=task_id[now].size();vis[now]=1;
	for(int p=0;p<num;p++){
		int id=task_id[now][p];
		deal(now,id);
	}
	for(int i=0;i<t[now].size();i++){
		if(vis[t[now][i]]) continue;
		dfs(t[now][i],now);
	}
	upd(now,pre,2);
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q;int res=q;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		t[u].push_back(v);
		t[v].push_back(u);
	}
	while(q--){
		cin>>pt>>k;
		task_id[pt].push_back(++cnt);
		for(int i=1,c;i<=k;i++){
			cin>>c;
			task_k[cnt].push_back(c);
		}
	}cnt=0;
	_init(1,0);
	build(1,n,1);
	// for(int i=1;i<=n;i++){
	// 	cout<<dfn[i]<<' ';
	// }cout<<endl;
	// for(int i=1;i<=n;i++){
	// 	cout<<dep[i]<<' ';
	// }cout<<endl;
	memset(vis,0,sizeof(vis));
	dfs(1,1);
	for(int i=1;i<=res;i++){
		cout<<reveal[i]<<endl;
	}
	return 0;
}