比赛链接

2022“杭电杯”中国大学生算法设计超级联赛（1）

7150. Static Query on Tree

给定一棵 /(n/) 个节点的树，每个节点只能向根节点走。 /(q/) 个询问，每次给定三个集合 /(A 、 B 、 C/) ，在 /(A 、 B 、 C/) 中分别取出 /(x, y, z/) ，问 /(x, y/) 往最终在 /(z/) 汇合， /(x, y/) 都经过的点有多少个

解题思路

树链剖分

将 /(A/) 和 /(B/) 中的点到根节点的路径打上标记，/(C/) 的子树的所有点打上标记，查询有三种标记的节点即为答案
可用 /(1,2,4/) 分别表示三种标记，维护区间与和区间或的信息，打上懒标记，每次询问查询区间与是否等于 /(7/)，同时每次查询后还需要一个区间清除的懒标记

• 时间复杂度：/(O(nlog^2n)/)

虚树

代码

• 树链剖分

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=2e5+5;
int t,n,q,fa[N],son[N],dep[N],id[N],sz[N],cnt,top[N];
vector<int> adj[N];
struct Tr
{
	int l,r,v1,v2,tag,clr;
}tr[N<<2];
void dfs(int x,int father,int depth)
{
	sz[x]=1,fa[x]=father,dep[x]=depth;
	for(int y:adj[x])
	{
		if(y==father)continue;
		dfs(y,x,depth+1);
		sz[x]+=sz[y];
		if(sz[son[x]]<sz[y])son[x]=y;
	}
}

void dfs1(int x,int t)
{
	id[x]=++cnt,top[x]=t;
	if(!son[x])return ;
	dfs1(son[x],t);
	for(int y:adj[x])
	{
		if(y==fa[x]||y==son[x])continue;
		dfs1(y,y);
	}
}
void pushup(int u)
{
	tr[u].v1=tr[u<<1].v1&tr[u<<1|1].v1;
	tr[u].v2=tr[u<<1].v2|tr[u<<1|1].v2;
}
void pushdown(int u)
{
	if(tr[u].clr)
	{
		tr[u<<1].clr=tr[u<<1|1].clr=1;
		tr[u<<1].v1=tr[u<<1].v2=tr[u<<1].tag=0;
		tr[u<<1|1].v1=tr[u<<1|1].v2=tr[u<<1|1].tag=0;
		tr[u].clr=0;
	}
	if(tr[u].tag)
	{
		tr[u<<1].v1|=tr[u].tag,tr[u<<1].v2|=tr[u].tag,tr[u<<1].tag|=tr[u].tag;
		tr[u<<1|1].v1|=tr[u].tag,tr[u<<1|1].v2|=tr[u].tag,tr[u<<1|1].tag|=tr[u].tag;
		tr[u].tag=0;
	}
}

void build(int u,int l,int r)
{
	tr[u]={l,r,0,0,0,0};
	if(l==r)return ;
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void update(int u,int l,int r,int k)
{
	if(l<=tr[u].l&&tr[u].r<=r)
	{
		tr[u].v1|=k;
		tr[u].v2|=k;
		tr[u].tag|=k;
		return ;
	}
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid)update(u<<1,l,r,k);
	if(r>mid)update(u<<1|1,l,r,k);
	pushup(u);
}
void update_path(int u,int v,int k)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		update(1,id[top[u]],id[u],k);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);
	update(1,id[u],id[v],k);
}
void update_tree(int u,int k)
{
	update(1,id[u],id[u]+sz[u]-1,k);
}
int ask(int u,int l,int r)
{
	if(l<=tr[u].l&&tr[u].r<=r)
	{
		if(tr[u].v1>=7)return tr[u].r-tr[u].l+1;
		if(tr[u].l==tr[u].r)return 0;
	}
	pushdown(u);
	int res=0;
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid&&tr[u<<1].v2>=7)res+=ask(u<<1,l,r);
	if(r>mid&&tr[u<<1|1].v2>=7)res+=ask(u<<1|1,l,r);
	return res;
}

int main()
{
    help;
    for(cin>>t;t;t--)
    {
    	cin>>n>>q;
    	for(int i=1;i<=n;i++)adj[i].clear();
    	for(int i=1;i<n;i++)
    	{
    		int r;
    		cin>>r;
    		adj[i+1].pb(r),adj[r].pb(i+1);
    	}
    	cnt=0;
    	dfs(1,0,1);
    	dfs1(1,1);
    	build(1,1,n);
    	while(q--)
    	{
    		int a,b,c,x;
    		cin>>a>>b>>c;
    		for(int i=1;i<=a;i++)
    		{
    			cin>>x;
    			update_path(1,x,1);
    		}
    		for(int i=1;i<=b;i++)
    		{
    			cin>>x;
    			update_path(1,x,2);
    		}
    		for(int i=1;i<=c;i++)
    		{
    			cin>>x;
    			update_tree(x,4);
    		}
    		cout<<ask(1,1,n)<<'/n';
    		tr[1].v1=tr[1].v2=tr[1].tag=0,tr[1].clr=1;
    	}
    }
    return 0;
}