C++ 解法, 执行用时: 692ms, 内存消耗: 93048K, 提交时间: 2021-12-08 14:00:59

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int s[N];
void add(int x)
{
    while (x<N-1){
        s[x]++;
        x+=x&(-x);
    }
}
int query(int x)
{
    int res=0;
    while (x){
        res+=s[x];
        x-=x&(-x);
    }
    return res;
}
long long f[N],a[N],g[N],dp[N],c[N];
vector<int> e[N];
void dfs(int u,int p)
{
    int res=0;
    for (auto it:e[u]){
        if(it==p) continue;
        int t=query(N-1)-query(a[u]-1);
        dfs(it,u);
        dp[it]=query(N-1)-query(a[u]-1)-t;
        f[u]+=dp[it];
        g[u]+=g[it];
    }
    g[u]+=f[u];
    add(a[u]);
}
void dfs2(int u,int p)
{
    for (auto it:e[u]){
        if(it==p) continue;
        g[it]=g[u]-dp[it]-f[it]+c[a[it]]-1;
        
        dfs2(it,u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    
    for (int i=1;i<=n;i++){
        c[a[i]]=query(N-1)-query(a[i]-1);
    }
    dfs2(1,0);
    for (int i=1;i<=n;i++) cout<<g[i]<<" ";
    return 0;
}