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)u1∑n​vu1∑n​i1∑n​f(u,v,i)对10 9 7 10^9 71097取模的值。† 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输入 #14 1 2 1 3 1 4输出 #19输入输出样例 #2输入 #26 1 2 2 3 3 4 4 5 5 6输出 #270输入输出样例 #3输入 #310 1 2 1 3 1 4 2 5 3 6 2 7 4 8 8 9 9 10输出 #3536说明/提示【样例解释】在样例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)1f ( 1 , 2 , 4 ) 1 f(1, 2, 4) 1f(1,2,4)1f ( 1 , 3 , 2 ) 1 f(1, 3, 2) 1f(1,3,2)1f ( 1 , 3 , 4 ) 1 f(1, 3, 4) 1f(1,3,4)1f ( 1 , 4 , 2 ) 1 f(1, 4, 2) 1f(1,4,2)1f ( 1 , 4 , 3 ) 1 f(1, 4, 3) 1f(1,4,3)1f ( 2 , 3 , 4 ) 1 f(2, 3, 4) 1f(2,3,4)1f ( 2 , 4 , 3 ) 1 f(2, 4, 3) 1f(2,4,3)1f ( 3 , 4 , 2 ) 1 f(3, 4, 2) 1f(3,4,2)1。【数据范围】本题采用捆绑测试且开启子任务依赖。子任务编号分值n ≤ n \len≤特殊性质子任务依赖1 118 8850 5050无无2 2215 1515400 400400无1 113 3324 24243000 30003000无1 , 2 1, 21,24 4417 17172 ⋅ 10 5 2 \cdot 10^52⋅105u i i , v i i 1 u_i i, v_i i 1ui​i,vi​i1无5 5536 36362 ⋅ 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实现#includebits/stdc.husingnamespacestd;#defineintlonglongconstintmod1e97;vectorintedge[200010];intsz[200010];intn,ans0;voiddfs(intu,intfa){sz[u]1;for(autov:edge[u]){if(vfa)continue;dfs(v,u);sz[u]sz[v];}if(u1)return;intsumn-sz[u];// 朝“上”子树大小anssum*(sum-1)/2*sz[u]sz[u]*(sz[u]-1)/2*sum;ans%mod;}signedmain(){cinn;for(inti1;in;i){intu,v;cinuv;edge[u].push_back(v);edge[v].push_back(u);}dfs(1,0);coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容