当前位置：首页 > news >正文

打卡信奥刷题（3505）用C++实现信奥题 P10842 【MX-J2-T3】Piggy and Trees

news 2026/8/13 10:46:56

P10842 【MX-J2-T3】Piggy and Trees

题目背景

原题链接：https://oier.team/problems/J2D。

题目描述

给你一棵n nn个结点的树。

定义f ( u , v , i ) f(u, v, i)f(u,v,i)为，在所有满足† dis ( u , x ) + dis ( v , x ) = dis ( u , v ) ^\dagger\text{dis}(u, x) + \text{dis}(v, x) = \text{dis}(u, v)†dis(u,x)+dis(v,x)=dis(u,v)的点x xx中，dis ( x , i ) \text{dis}(x, i)dis(x,i)的最小值。

求∑ u = 1 n ∑ v = u + 1 n ∑ i = 1 n f ( u , v , i ) \sum\limits_{u = 1}^n \sum\limits_{v = u + 1}^n \sum\limits_{i = 1}^n f(u, v, i)u=1∑nv=u+1∑ni=1∑nf(u,v,i)对10 9 + 7 10^9 + 7109+7取模的值。

† dis ( u , v ) ^\dagger\text{dis}(u, v)†dis(u,v)为树上u , v u, vu,v两点的路径长度。特别地，dis ( u , u ) = 0 \text{dis}(u, u) = 0dis(u,u)=0。

输入格式

第一行包含一个整数n nn，表示树的结点数。

之后的n − 1 n - 1n−1行中的第i ii行包含两个整数u i , v i u_i, v_iui,vi，表示树上的一条边。

输出格式

输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

4 1 2 1 3 1 4

输出 #1

输入输出样例 #2

输入 #2

6 1 2 2 3 3 4 4 5 5 6

输出 #2

输入输出样例 #3

输入 #3

10 1 2 1 3 1 4 2 5 3 6 2 7 4 8 8 9 9 10

输出 #3

说明/提示

【样例解释】

在样例1 11中，所有非0 00的f ( u , v , i ) f(u, v, i)f(u,v,i)的值为：

f ( 1 , 2 , 3 ) = 1 f(1, 2, 3) = 1f(1,2,3)=1；
f ( 1 , 2 , 4 ) = 1 f(1, 2, 4) = 1f(1,2,4)=1；
f ( 1 , 3 , 2 ) = 1 f(1, 3, 2) = 1f(1,3,2)=1；
f ( 1 , 3 , 4 ) = 1 f(1, 3, 4) = 1f(1,3,4)=1；
f ( 1 , 4 , 2 ) = 1 f(1, 4, 2) = 1f(1,4,2)=1；
f ( 1 , 4 , 3 ) = 1 f(1, 4, 3) = 1f(1,4,3)=1；
f ( 2 , 3 , 4 ) = 1 f(2, 3, 4) = 1f(2,3,4)=1；
f ( 2 , 4 , 3 ) = 1 f(2, 4, 3) = 1f(2,4,3)=1；
f ( 3 , 4 , 2 ) = 1 f(3, 4, 2) = 1f(3,4,2)=1。

【数据范围】

本题采用捆绑测试且开启子任务依赖。

子任务编号	分值	n ≤ n \len≤	特殊性质	子任务依赖
1 11	8 88	50 5050	无	无
2 22	15 1515	400 400400	无	1 11
3 33	24 2424	3000 30003000	无	1 , 2 1, 21,2
4 44	17 1717	2 ⋅ 10 5 2 \cdot 10^52⋅105	u i = i , v i = i + 1 u_i = i, v_i = i + 1ui=i,vi=i+1	无
5 55	36 3636	2 ⋅ 10 5 2 \cdot 10^52⋅105	无	1 , 2 , 3 , 4 1, 2, 3, 41,2,3,4

对于所有数据，满足2 ≤ n ≤ 2 ⋅ 10 5 2 \le n \le 2 \cdot 10^52≤n≤2⋅105，输入的图是一棵树。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintmod=1e9+7;vector<int>edge[200010];intsz[200010];intn,ans=0;voiddfs(intu,intfa){sz[u]=1;for(autov:edge[u]){if(v==fa)continue;dfs(v,u);sz[u]+=sz[v];}if(u==1)return;intsum=n-sz[u];// 朝“上”子树大小ans+=sum*(sum-1)/2*sz[u]+sz[u]*(sz[u]-1)/2*sum;ans%=mod;}signedmain(){cin>>n;for(inti=1;i<n;i++){intu,v;cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}dfs(1,0);cout<<ans;return0;}