题解：CF2063E Triangle Tree

TTpandaS · 2025-01-23 21:18:38 · 题解

赛时做完 C 后 5 min 切 E，全球 4 杀，然后因为用的是临时邮箱注册的小号，号被封了，我上早八。

对于一对 (u,v)，贡献为 |dist(u,lca(u,v))+dist(v,lca(u,v))|-|dist(u,lca(u,v))-dist(v,lca(u,v))|+1，经典绝对值与 \min,\max 互换，等价于 2 \times \min(dist(u,lca(u,v)),dist(v,lca(u,v)))-1，考虑先将答案减去 \dfrac{n\times(n-1)}{2}，但是成祖先关系的点对不需要减，且成祖先关系的点对数量为 \sum_{x \in V} dep_x，加上即可。

剩下就是求 \sum_{u,v \in V}2 \times \min(dist(u,lca(u,v)),dist(v,lca(u,v)))，因为 u,v 与 lca(u,v) 成祖先关系，所以 dist(u,lca(u,v))=dep_u-dep_{lca(u,v)}，提取出来就是 \sum_{u,v \in V}2 \times (\min(dep_u,dep_v)-dep_{lca(u,v)})，所以计算每个点作为 lca 的次数即可，可以通过一个 dfs 解决。对于 \sum_{u,v \in V}2 \times \min(dep_u,dep_v)，直接按照 dep 排序，dep_i 贡献次数就是 n-i。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int T;
int n,ans;
vector<int> g[N];
int siz[N],dep[N];
void dfs(int x,int fa){
    dep[x]=dep[fa]+1,siz[x]=1;
    int sum=1,tot=0;
    for(int y:g[x]){
        if(y==fa) continue;
        dfs(y,x);
        siz[x]+=siz[y],tot+=siz[y]*sum,sum+=siz[y];
    }
    ans-=2*dep[x]*tot;
}
void solve(){
    cin>>n;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        g[x].push_back(y),g[y].push_back(x);
    }
    ans=-n*(n-1)/2;
    dfs(1,0);
    sort(dep+1,dep+n+1);
    for(int i=1;i<=n;i++){
        ans+=2*dep[i]*(n-i)+(dep[i]-1);
        g[i].clear();
    }
    cout<<ans<<endl;
}
signed main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}