本文共 2725 字，大约阅读时间需要 9 分钟。

解题思路：点分治。对于每一个重心，找到当前子树的所有符合条件的。

#include
   
    using namespace std;typedef long long ll;typedef long double lf;typedef unsigned long long ull;typedef pair
    
     P;const int inf = 0x7f7f7f7f;const ll INF = 1e16;const int N = 2e5+10;const ull base = 131;const ll mod =  998244353;inline int read(){   int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){   if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){   x=x*10+ch-'0';ch=getchar();}return x*f;}inline string readstring(){   string str;char s=getchar();while(s==' '||s=='\n'||s=='\r'){   s=getchar();}while(s!=' '&&s!='\n'&&s!='\r'){   str+=s;s=getchar();}return str;}int random(int n){   return (int)(rand()*rand())%n;}void writestring(string s){   int n = s.size();for(int i = 0;i < n;i++){   printf("%c",s[i]);}}bool is_prime(int n){   if(n <2) return false;for(int i = 2;i*i <= n;i++){   if(n%i == 0) return false;}return true;}struct str{       int dot;    int dis;    int next;}e[N<<4];int head[N<<4],C = 0;void add(int u,int v,int z){       e[++C].dis = z;    e[C].dot = v;    e[C].next = head[u];    head[u] = C;}ll val[N];int dp[N];int sum,rt;int size[N],vis[N];void getrt(int u,int fa){       size[u] = 1;dp[u] = 0;    for(int i = head[u];i;i = e[i].next){           int v = e[i].dot;        if(v == fa|| vis[v]) continue;        getrt(v,u);        size[u] += size[v];        dp[u] = max(dp[u],size[v]);    }    dp[u] = max(dp[u],sum-size[u]);    if(dp[u] < dp[rt]) rt = u;}int tot,dis[N];struct node{       ll val;    int dis;    int dot;}a[N];void getdis(int u,int fa){       a[++tot].val = val[u];    a[tot].dis = dis[u];    a[tot].dot = u;    for(int i = head[u];i;i = e[i].next){           int v = e[i].dot;        if(v == fa || vis[v]) continue;        dis[v] = dis[u]+e[i].dis;        getdis(v,u);    }}bool cmp(node a,node b){       return a.val < b.val;}ll ans = 0;ll calc(int u,int w){       tot = 0;dis[u] = w;    getdis(u,0);    sort(a+1,a+1+tot,cmp);    ll ret = 0,sum = 0;    /*    for(int i = 1;i <= tot;i++){        for(int j = i+1;j <= tot;j++){            ret = (ret+a[i].val*(a[i].dis+a[j].dis))%mod;        }    }    */    for(int i = 1;i <= tot;i++){           sum = (sum+a[i].dis)%mod;    }    for(int i = 1;i < tot;i++){           ll x = a[i].val,y = a[i].dis;        sum = (sum-y+mod)%mod;        ll len = tot-i;        y = (len*x*y)%mod;        x = (x*sum)%mod;        ret = (ret+x+y)%mod;    }    ret = (ret+ret)%mod;    return ret;}void solve(int u){       vis[u] = 1;    //cout<<
     
      <= n;i++){           val[i] = read();    }    for(int i = 1;i < n;i++){           int u = read(),v = read();        add(u,v,1);        add(v,u,1);    }    dp[0] = inf;sum = n;rt = 0;    getrt(1,0);    solve(rt);    cout<
      
       <
      
     
    
   

转载地址：http://rkqp.baihongyu.com/