QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61995#4387. Static Query on Treeluyiming123TL 0ms0kbC++144.5kb2022-11-16 16:26:332022-11-16 16:26:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-16 16:26:33]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-11-16 16:26:33]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int Test,n,q;
int NA,NB,NC;
vector <int> g[N];
int siz[N],top[N],dfn[N],son[N],dep[N],f[N],dfntot = 0;
template <typename T> void read(T &x)
{
	int w = 1; x = 0; char ch = getchar();
	while(!isdigit(ch))
	{
		if(ch == '-') w = -1;
		ch = getchar();
	}
	while(isdigit(ch))
	{
		x = x * 10 + ch - '0'; ch = getchar();
	}
	x *= w; return;
}
struct node
{
	bool val[3],tag[3];
}T[N << 2];
void pushup(int root)
{
	for(int i = 0; i <= 2; i++) 
		T[root].val[i] = T[root << 1].val[i] & T[root << 1 | 1].val[i];
	return;
}
void build(int root,int l,int r,int opt)
{
	T[root].val[opt] = T[root].tag[opt] = 0;
	if(l == r) 
	{
		return;
	}
	int mid = (l + r) >> 1;
	build(root << 1, l,mid,opt),build(root << 1 | 1, mid + 1,r,opt);
	return;
}
void pushdown(int root,int l,int r,int opt)
{
	if(T[root].tag[opt] == 0) return; bool tag = T[root].tag[opt];
	T[root << 1].val[opt] |= tag,T[root << 1 | 1].val[opt] |= tag;
	T[root << 1].tag[opt] |= tag,T[root << 1 | 1].tag[opt] |= tag;
	T[root].tag[opt] = 0;
	return;
}
void update(int root,int l,int r,int s,int t,bool d,int opt)
{
//	printf("UPD : l = %d,r = %d,s = %d,t = %d,opt = %d\n",l,r,s,t,opt);
	if(l <= s && t <= r) 
	{
		T[root].val[opt] |= d,T[root].tag[opt] |= d;
		return;
	}
	pushdown(root,s,t,opt);
	int mid = (s + t) >> 1;
	if(l <= mid) update(root << 1,l,r,s,mid,d,opt);
	if(r > mid) update(root << 1 | 1,l,r,mid + 1,t,d,opt);
	pushup(root); return;
}
bool query(int root,int l,int r,int x,int opt)
{
	if(l == r) return T[root].val[opt];
	pushdown(root,l,r,opt);
	int mid = (l + r) >> 1;
	if(x <= mid) return query(root << 1,l,mid,x,opt);
	else return query(root << 1 | 1,mid + 1,r,x,opt);
}
void Pr(int root,int l,int r)
{
//	printf("root = %d,l = %d,r = %d,val0 = %d,va1l = %d,val2 = %d\n",root,l,r,T[root].val[0],T[root].val[1],T[root].val[2]);
	if(l == r) return; int mid = (l + r) >> 1;
	Pr(root << 1,l,mid),Pr(root << 1 | 1,mid + 1,r); return ;
}
void dfs1(int x,int fa)
{
	siz[x] = 1,f[x] = fa,dep[x] = dep[fa] + 1;
	for(int i = 0; i < (int)g[x].size(); i++)
	{
		int v = g[x][i];
		if(v == fa) continue;
		dfs1(v,x);
		siz[x] += siz[v]; 
		if(son[x] == 0 || siz[v] > siz[son[x]]) son[x] = v;
	}
	return;
}
void dfs2(int x,int t)
{
	top[x] = t;
	dfn[x] = ++dfntot;
	if(son[x]) dfs2(son[x],t);
	for(int i = 0; i < (int)g[x].size(); i++)
	{
		int v = g[x][i];
		if(v == f[x] || v == son[x]) continue;
		dfs2(v,v);
	}
	return;
}
void Modify_Path(int x,int y,bool d,int opt)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] > dep[top[y]]) swap(x,y);
		update(1,dfn[top[y]],dfn[y],1,dfntot,d,opt),y = f[top[y]];
	}
	if(dfn[x] > dfn[y]) swap(x,y); 
	update(1,dfn[x],dfn[y],1,dfntot,d,opt);
	return;
}
void Modify_Subtree(int x,bool d,int opt)
{
	update(1,dfn[x],dfn[x] + siz[x] - 1,1,dfntot,d,opt); return;
}
int Find(int root,int l,int r)
{
	for(int i = 0; i < 3; i++)pushdown(root,l,r,i);
	bool flag = 1;
	for(int i = 0; i < 3; i++) 
		if(!T[root].val[i]) {flag = 0; break;
		}
	if(flag == 1) return r - l + 1; 
	else if(l == r) return 0;
	int mid = (l + r) >> 1;
	int ans = Find(root << 1,l,mid) + Find(root << 1 | 1,mid + 1,r);
	return ans;
}
int main(void)
{	
	read(Test);
	while(Test--)
	{
		read(n),read(q);
		for(int i = 1; i <= n; i++) g[i].clear();
		for(int i = 2; i <= n; i++)
		{
			int f; read(f);
			g[f].push_back(i),g[i].push_back(f);
		}
		
		dfs1(1,0),dfs2(1,1);
//		for(int i = 1; i <= n; i++) 
//			fprintf(stderr,"dep[%d] = %d,dfn[%d] = %d,siz[%d] = %d,top[%d] = %d,son[%d] = %d\n",i,dep[i],i,dfn[i],i,siz[i],i,top[i],i,son[i]);
		while(q--)
		{
			read(NA),read(NB),read(NC);
			
			for(int i = 0; i < 3; i++) build(1,1,dfntot,i);
//			vector <pair<int,int> > OptA,OptB;
			for(int i = 1; i <= NA; i++) 
			{
				int x; scanf("%d",&x);
//				fprintf(stderr,"MP: i = %d\n",i);
				Modify_Path(1,x,1,0); //OptA.push_back({x,0});
//				fprintf(stderr,"Final.\n");
			}
			for(int i = 1; i <= NB; i++)
			{
				int x; scanf("%d",&x);
				Modify_Path(1,x,1,1); //OptA.push_back({x,1});
			}
			for(int i = 1; i <= NC; i++)
			{
				int x; scanf("%d",&x);
				Modify_Subtree(x,1,2);// OptB.push_back({x,2});
			}
//			Pr(1,1,n);
			int total = Find(1,1,n);
			printf("%d\n",total);
//			for(int i = 0; i < (int)OptA.size(); i++) Modify_Path(1,OptA[i].first,-1,OptA[i].second);
//			for(int i = 0; i < (int)OptB.size(); i++) Modify_Subtree(OptB[i].first,-1,OptB[i].second);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

1
200000 18309
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:


result: