Hangzhou electric school game 2 1001 2022 Static Query on Tree (Tree + hash table difference chain subdivision

题目传送门：Static Query on Tree

题目大意：

给定一棵根为1的树,给定点集A,B,C,能被AEither one arrives,BEither one arrives,且能达到Cthe number of points for any one of .

This is the second multi-school,Complete the sign-in question,就开了1001.In fact, after understanding the subject,The idea came quickly,At that time, I gave my teammates an algorithm,如果能把Csubtree coloring,在把A,BEvery point arrives1All on the path are marked with a mark,The last statistic saved the answer.但是不知道该怎么操作,赛后看题解,树链剖分！

Sure enough, there is still no culture to eat(数据结构)的亏,Spent two days in oxbushu dissection,Finally got this questionA了.

I was going to write a line segment tree,But there are only three colors that come to mind,Just a little trick,Write less segment trees,The code shrinks immediately90行

#include<bits\stdc++.h>
using namespace std;
const int maxn=2e5+5;
#define ll long long 
int n,m,na,nb,nc;
int sz[maxn],son[maxn],fa[maxn],top[maxn],cnt=0,nid[maxn],dep[maxn];
int a[maxn],b[maxn],c[maxn];
vector<int>e[maxn];
ll tr[maxn];
map<int,ll>add;
void dfs1(int s,int father)
{
    
    fa[s]=father;
    sz[s]=1,dep[s]=dep[father]+1;
    for(auto to:e[s])
    {
    
        if(to==father)continue;
        dfs1(to,s);
        sz[s]+=sz[to];
        if(sz[son[s]]<sz[to])son[s]=to;
    }
}
void dfs2(int s,int t)
{
    
    nid[s]=++cnt;top[s]=t;
    if(!son[s])return ;
    dfs2(son[s],t);
    for(auto to:e[s])
    {
    
        if(to==fa[s]||to==son[s])continue;
        dfs2(to,to);
    }
}
void add_path(int u,int v,ll y)
{
    
    while(top[u]!=top[v])
    {
    
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        add[nid[top[u]]]+=y;add[nid[u]+1]-=y;
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    add[nid[u]]+=y;add[nid[v]+1]-=y;
}
void add_tree(int u,ll y)
{
    
    add[nid[u]]+=y;
    add[nid[u]+sz[u]-1+1]-=y;
}
const ll p1=1;
const ll p2=1e6;
const ll p3=1e12;
void solve()
{
    
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)nid[i]=0,e[i].clear(),top[i]=0,fa[i]=0,son[i]=0,sz[i]=0,tr[i]=0;
    for(int i=2;i<=n;i++)
    {
    
        int u;
        scanf("%d",&u);
        e[u].push_back(i);
        e[i].push_back(u);
    }
	dfs1(1,0);
    dfs2(1,1);
    while(m--){
    
    scanf("%d%d%d",&na,&nb,&nc);
    for(int i=1;i<=na;i++)scanf("%d",&a[i]);
    for(int i=1;i<=nb;i++)scanf("%d",&b[i]);
    for(int i=1;i<=nc;i++)scanf("%d",&c[i]);
    for(int i=1;i<=na;i++)add_path(1,a[i],(ll)p1);
    for(int i=1;i<=nb;i++)add_path(1,b[i],(ll)p2);
    for(int i=1;i<=nc;i++)add_tree(c[i],(ll)p3);
    ll ans=0;int cnt=0,las=-1;
    for(auto it:add){
    
        ans+=it.second;
        if(ans%p2>0&&(ans%p3)/p2>0&&ans/p3>0){
    if(las==-1)las=it.first;}
        else if(las!=-1)cnt+=(it.first-las),las=-1;
	}
    printf("%d\n",cnt);
    add.clear();
	}
}
int main()
{
    
    int t;
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}