题解 | #写轮眼#

可以使用map实现的树上启发式合并解决。关于信息，对于每个节点 ，往上传小于 的信息和 的信息。关于计算答案，在合并时统计该点作为权值小于 的点的路径部分和该点作为路径始发点。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int mod=998244353; 
const int N=2e5+10;
int n,head[N],nxt[N<<1],to[N<<1],cnt,val[N],siz[N],ans;
vector<map<int,int,greater<int> > >vr;
void add(int u,int v){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa){
    siz[u]=1;
    int zz=0,dz=0;
    for(int i=head[u];i!=-1;i=nxt[i]){
        int v=to[i];
        if(v!=fa){
            dfs(v,u);
            siz[u]+=siz[v];
            if(siz[v]>dz){
                zz=v;
                dz=siz[v];
            }
        }
    }
    if(zz){
        swap(vr[u],vr[zz]);
        int sum=0;
        set<int>st;
        for(int i=head[u];i!=-1;i=nxt[i]){
            int v=to[i];
            if(v!=fa&&v!=zz){
                for(pii x:vr[v]){
                    vr[u][x.first]+=x.second;
                    if(x.first<val[u])ans+=(vr[u][x.first]-x.second)*x.second;
                }
                vr[v].clear();
            }
        }
        for(pii p:vr[u]){
            if(p.first<val[u])break;
            if(p.first==val[u])ans+=p.second;
            st.insert(p.first);
        }

        for(int x:st)vr[u].erase(x);
    }
    vr[u][val[u]]=1;
}
void solve(){
    cin>>n;
    cnt=ans=0;
    for(int i=1;i<=n;i++)head[i]=-1;
    vr=vector<map<int,int,greater<int> > >(n+1,map<int,int,greater<int> >{});
    for(int i=1;i<=n;i++)cin>>val[i];
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    cout<<ans*2<<"\n";
}
signed main(){
    ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    solve();
}