2022年杭电多校第2场 1001 Static Query on Tree（树链剖分+哈希表差分

题目传送门：Static Query on Tree

题目大意：

给定一棵根为1的树，给定点集A,B,C，能被A任意一个到达，B任意一个到达，且能达到C的任意一个的点的数量。

这是第二场多校，写完签到题，就开了1001。其实看懂题目之后，思路还是挺快就出现了，当时就给队友口胡了一种算法，如果能把C的子树染色，在把A,B每一个点到1的路径上的全部打上个标记，最后统计一下答案救过了。但是不知道该怎么操作，赛后看题解，树链剖分！

果然还是吃了没文化(数据结构)的亏，花了两天在恶补树剖，终于把这题给A了。

本来打算写线段树的，但是想到就只有三种颜色，用点小技巧就可以过了,少写线段树，代码立马缩减90行

#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;
}