本题最优解。

思路

对于点 $u$，和一个点对 $(r,s)$，如第一棵树中，$r$ 是 $u$ 的祖先且第二棵树中 $s$ 是 $u$ 的祖先，$u$ 的答案就加一。

换个角度，我们考虑每个点对，通过 $\text{dfs}$ 序判断其子树范围。把两个范围想象成平面上的一个矩形，如果一个点 $u$ 在两棵树中 $\text{dfs}$ 序形成的坐标在该矩形中，$u$ 的答案就加一。

可能不好理解，用样例的图举个例子。

如果有一个点对 $(3,2)$。

第一个范围就是点 $3$ 在第一棵树中的子树的 $\text{dfs}$ 序范围，即 $[3,3]$。

第二个范围是点 $2$ 在第二棵树中的子树的 $\text{dfs}$ 序范围，即 $[1,3]$。

将这两个范围想象成平面中的一个矩形 $[3,3]\times [1,3]$。

点 $3$ 在两棵树中的 $\text{dfs}$ 序分别为 $3,3$，把它想象成平面中的点 $(3,3)$。这个点在矩形 $[3,3]\times [1,3]$ 中，所以点 $3$ 的答案加一。

这就是扫描线板子。

本题中 $\text{dfs}$ 的顺序就是扫描线的移动顺序，所以可以在 $\text{dfs}$ 中修改。

时间复杂度 $O((n+m)\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m,r,s;
const ll N=2e5+10;
ll fa[3][N],siz[3][N],dfn[3][N],tot[3],root[3],ans[N];
vector<ll>e[3][N],add[N];
struct fenwick_tree{
    ll tr[N];
    #define low(i) (i&(-i))
    void clear(){for(ll i=0;i<=n;i++)tr[i]=0;}
    void add(ll i,ll k){for(;i<=n;i+=low(i))tr[i]+=k;}
    void upd(ll l,ll r,ll k){add(l,k),add(r+1,-k);}
    ll ask(ll i){
        ll res=0;
        for(;i;i-=low(i))res+=tr[i];
        return res;
    }
}tr;
void dfs1(ll u,ll l){
    siz[l][u]=1,dfn[l][u]=++tot[l];
    for(ll v:e[l][u]){
        dfs1(v,l);
        siz[l][u]+=siz[l][v];
    }
}
void dfs2(ll u){
    for(ll k:add[u])tr.upd(dfn[2][k],dfn[2][k]+siz[2][k]-1,1);
    ans[u]=tr.ask(dfn[2][u]);
    for(ll v:e[1][u])dfs2(v);
    for(ll k:add[u])tr.upd(dfn[2][k],dfn[2][k]+siz[2][k]-1,-1);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll l:{1,2}){
            cin>>fa[l][i];
            if(fa[l][i])e[l][fa[l][i]].emplace_back(i);
            else root[l]=i;
        }
    }
    for(ll l:{1,2})dfs1(root[l],l);
    for(ll i=1;i<=m;i++){
        cin>>r>>s;
        add[r].emplace_back(s);
    }
    dfs2(root[1]);
    for(ll i=1;i<=n;i++)cout<<ans[i]<<"\n";
    return 0;
}

最后，希望本篇题解对你有所帮助，感谢观看。