专栏文章

题解：CF2063E Triangle Tree

TTTpandaS
CF2063E题解参与者 6已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@miqesur2
此快照首次捕获于
2025/12/04 03:37
3 个月前
此快照最后确认于
2025/12/04 03:37
3 个月前
查看原文
赛时做完 C 后 5 min 切 E，全球 4 杀，然后因为用的是临时邮箱注册的小号，号被封了，我上早八。
对于一对 (u,v)(u,v)，贡献为 ∣dist(u,lca(u,v))+dist(v,lca(u,v))∣−∣dist(u,lca(u,v))−dist(v,lca(u,v))∣+1|dist(u,lca(u,v))+dist(v,lca(u,v))|-|dist(u,lca(u,v))-dist(v,lca(u,v))|+1，经典绝对值与 min⁡,max⁡\min,\max 互换，等价于 2×min⁡(dist(u,lca(u,v)),dist(v,lca(u,v)))−12 \times \min(dist(u,lca(u,v)),dist(v,lca(u,v)))-1，考虑先将答案减去 n×(n−1)2\dfrac{n\times(n-1)}{2}，但是成祖先关系的点对不需要减，且成祖先关系的点对数量为 ∑x∈Vdepx\sum_{x \in V} dep_x，加上即可。
剩下就是求 ∑u,v∈V2×min⁡(dist(u,lca(u,v)),dist(v,lca(u,v)))\sum_{u,v \in V}2 \times \min(dist(u,lca(u,v)),dist(v,lca(u,v)))，因为 u,vu,v 与 lca(u,v)lca(u,v) 成祖先关系，所以 dist(u,lca(u,v))=depu−deplca(u,v)dist(u,lca(u,v))=dep_u-dep_{lca(u,v)}，提取出来就是 ∑u,v∈V2×(min⁡(depu,depv)−deplca(u,v))\sum_{u,v \in V}2 \times (\min(dep_u,dep_v)-dep_{lca(u,v)})，所以计算每个点作为 lca 的次数即可，可以通过一个 dfs 解决。对于 ∑u,v∈V2×min⁡(depu,depv)\sum_{u,v \in V}2 \times \min(dep_u,dep_v)，直接按照 dep 排序，depidep_i 贡献次数就是 n−in-i。
CPP
#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;
}

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...