题意：

给出一片森林，问能找到多少个三元组(x,y,z)满足f[y]>f[x]和f[z]>f[x]，并且x是y的祖先，y是z的祖先。

思路：

对于每个点作为y，答案为y的祖先中f比它小的乘以y的子树中f比它小的。y的子树中f比它小的，之前上一篇博文中用dfs序解决了这个问题，但是这里考虑到这里比较的不是编号而是f，所以像那个做法比较麻烦，所以可以考虑另一种做法，对于一个点，进入它的时候查询当前比它小的结点数（用树状数组维护权值），从它出来的时候查询当前比它小的结点数，两者相减就是子树中比它小的结点数。

y的祖先中f比它小的，可以在进入的时候查询当前比它小的结点，出来的时候也要把它从树状数组里删除，这样可以保证每次查询的时候只有祖先。

所以这样每棵树只要搜一次，最后把答案相加即可。

这道题目卡内存，所以为了省内存，因为这是一棵树，而且肯定是从根结点搜下来的，所以可以只保存从父节点到子结点的那条边，vis数组也可以省略。

代码：

typedef long long ll;
vector<int>v[1000010];
int fa[1000010];
int w[1000010];
int d1[1000010],d2[1000010];
ll tot;
int lowbit(int x)
{
    return x&(-x);
}
int query(int a[],int x)
{
    int res=0;
    while(x)
    {
        res+=a[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int a[],int x,int v)
{
    while(x<=1000000)
    {
        a[x]+=v;
        x+=lowbit(x);
    }
}
void dfs(int id,int par)
{
    int in=query(d1,w[id]-1);
    add(d1,w[id],1);
    add(d2,w[id],1);
    for(int i=0;i<v[id].size();i++)
    {
        if(v[id][i]!=par)
            dfs(v[id][i],id);
    }
    add(d2,w[id],-1);
    tot+=(ll)(query(d1,w[id]-1)-in)*query(d2,w[id]-1);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            v[i].clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&fa[i]);
            if(fa[i]!=0)
            {
                //v[i].push_back(fa[i]);
                v[fa[i]].push_back(i);
            }
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&w[i]);
        tot=0;
        memset(d1,0,sizeof(d1));
        memset(d2,0,sizeof(d2));
        for(int i=1;i<=n;i++)
            if(fa[i]==0)
                dfs(i,i);
        printf("%lld\n",tot);
    }
    return 0;
}