滑稽树下你和我-树形dp-吉首大学2019年程序设计竞赛

题目链接https://ac.nowcoder.com/acm/contest/992/J时间限制C/C 1秒其他语言2秒空间限制C/C 32768K其他语言65536K64bit IO Format: %lld题目描述红红和蓝蓝是随机降生在苹果树上的苹果仙灵现在红线仙想估测他们的CP系数并决定是否使他们成为一对CP。给出n个结点n-1条边的树节点编号为1到n,定义distance(i,j)为i与j的树上距离。CP系数是指所有红红和蓝蓝在不同位置i,j的distance(i,j)之和。即 \sum_{i1}^{n-1}{\sum_{ji1}^{n}{distance(i,j)}}∑i1n−1​∑ji1n​distance(i,j)。求红红和蓝蓝的CP系数对1097取模。输入描述:第一行一个整数n 1 n 105 ),表示树的结点个数。随后n-1行每行三个整数a,b,c ( 1 a,b n ),( 0 c 109 )表示结点a,b之间有一条权值为c的边,( a \ne​ b )。输出描述:一行一个整数表示CP系数对1097取模的结果。这题一眼看过去就能让人想起树形dp那就按树形dp思维走一走。树形dp的状态转换就是在原有的已u为根的子树基础上每新增一个子树连接成一棵新的树。我们要做的就是在状态转换过程中维护好数据。分情况对于新增一个点u若它做出贡献情况1u为某路线的一端点情况2u在某路线上但不在端点上状态转换时的维护接下来我们描述“以u为根的子树”为“u子树”纯粹省字我们设两个dp:dp1[u]表示u子树所包含的节点个数包括u本身dp0[u]表示u子树中u到每个节点的距离和。假设u的父节点为u_fa有了这两个东东我们就能在状态转换过程中维护好u_fa的dp0和dp1即dp0[u_fa]和dp1[u_fa]。首先dp1[u_fa]dp1[u] 这个很好理解。其次dp0[u_fa]dp0[u_fa]dp0[u]dp1[u]*distance(u_fa,u); 就是把u分别连接上v子树的每个节点即dp1[u]条路线这些路线用了dp1[u]次distance(u_fa,u),再加上dp0[u]不就成了dp0[u_fa]了。脑补一下计算答案知道了这两个变量如何维护接下来就是思考如何算出答案ret了。对上面的情况1 dp0[u]其实就表示了u的所有贡献了。对上面的情况2u其实就被当做中继节点了。对u的一个儿子v对应的v子树来说v子树上的每个点都可以经过u连接dp1[u]-dp1[v]-1条路线连出去这样一算distance(u,v)走了(dp1[u]-dp1[v]-1)*dp1[v]次。那么dp0[v]也贡献了(dp1[u]-dp1[v]-1)次。那么情况2总共就是要加上distance(u,v)*(dp1[u]-dp1[v]-1)*dp1[v](dp1[u]-dp1[v]-1)*dp0[v]。结论总结每计算一个点u那么:上式中v为u的某个儿子。接下来上程序#include cstdio #include string.h #include algorithm #include stdio.h #include math.h #include queue using namespace std; typedef long long ll; const int max_n1e510; const int mod 1e97; ll dp0[max_n],dp1[max_n];//dp0:sum_l dp1:sum_son int h[max_n]; int num; ll ret; struct Edge { int u,v,next; ll l; }e[max_n1]; void add_edge(int u,int v,ll l) { e[num].uu; e[num].vv; e[num].ll; e[num].nexth[u]; h[u]num; } void dfs(int u,int fa) { dp1[u]1; ll son0; for(int ih[u];i!-1;ie[i].next) { int ve[i].v; if(vfa) continue; son; dfs(v,u); dp1[u]dp1[v]; dp0[u](dp0[u]dp0[v]dp1[v]*e[i].l%mod)%mod; } ret(retdp0[u])%mod; for(int ih[u];i!-1;ie[i].next) { int ve[i].v; if(vfa) continue; ret(rete[i].l*(dp1[u]-dp1[v]-1)%mod*dp1[v]%mod(dp1[u]-dp1[v]-1)*dp0[v]%mod)%mod; } } int main() { int n; while(scanf(%d,n)!EOF) { num0; memset(h,-1,sizeof(h)); memset(dp0,0,sizeof(dp0)); memset(dp1,0,sizeof(dp1)); int a,b,c; ret0; for(int i1;in;i) { scanf(%d%d%d,a,b,c); add_edge(a,b,(ll)c); add_edge(b,a,(ll)c); } dfs(1,0); printf(%lld\n,ret); } }