咦？树状数组？二维数点？那是什么？

大家好，因为我非常喜欢 dsu，于是我用 dsu 过了这题。

经典结论：一个点的子树的 dfn 序是连续的一个区间。

于是把 dfn 序跑出来，一个点是另一个点的子孙当且仅当这个点的 dfn 序在对方子树 dfn 序对应的区间内。

接着扔到另一棵树上计数，抽象成每个点有一个要求和一个权值，对于每个点我们需要求出其子树内点的权值在要求的区间内的数量。

这个问题其实可以直接用前缀和的思想拆开来，变成求子树内比某个数小的数字个数。

刚刚想到的一个做法。

考虑树剖。

然后变成求区间内比 $k$ 小的数字数量。

莫队或者主席树都可以实现。

子树信息可以合并，考虑 dsu on tree！

直接 pbds 维护子树内所有编号然后把区间端点扔进去查排名，减一下就算完了。

时间复杂度 $O(n\log^2 n)$，完全胜利！

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#define int long long
using namespace std;
vector<int>v1[100005],v2[100005];
int fa[100005];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>st[100005];
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(st[x].size()<st[y].size())swap(x,y);
    for(int i:st[y])st[x].insert(i);
    fa[y]=x;
}
int dfn[100005],dfnn;
int r[100005];
void dfs(int x){
    dfn[x]=++dfnn;
    for(int i:v1[x])
    dfs(i);
    r[x]=dfnn;
}
int ans;
void dfss(int x){
    for(int i:v2[x]){
        dfss(i);
        merge(x,i);
    }
    int qwq=x;
    x=find(x);
    ans+=((int)(st[x].order_of_key(r[qwq]+1)-st[x].order_of_key(dfn[qwq]+1)));
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    fa[i]=i;
    int rt1,rt2;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x)v1[x].push_back(i);
        else rt1=i;
    }
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x)v2[x].push_back(i);
        else rt2=i;
    }
    dfs(rt1);
    for(int i=1;i<=n;i++)
    st[i].insert(dfn[i]);
    dfss(rt2);
    cout<<ans;
    return 0;
}
// 扎实踏稳脚步，路易斯使劲握紧擒住古莲脑袋的手。
// 然后就这么扭过上半身，以惊人之势把古莲猛力抛出窗外。

//「来喔～你最爱的飞行魔术时间到了！」

//「嘎啊────！」
// 飞舞在空中的古莲，哀号声响彻平稳的午后高级住宅区。

// 另外，关于这番暴行，前顽童的说词是「也不过才二楼，死不了人的吧。我可是被臭老头从三楼研究室直接弄下去过喔」。

哦这里有一个番外做法。其实这是我的第一版做法。

考虑给边定向，父亲指向儿子。

于是强化为判有多少个点对在两个 DAG 上均可达。

诶，我们大力上 bitset，时间复杂度 $O(\frac{n^2}\omega)$，还真不是不行？

注意到空间不是追忆，于是还是爆炸了。嘟。