树形DP--求树上任意两点间距离和

例题：HDU2376 HDU6446（2018CCPC网络赛）

思路：求任意两点间距离和可以转换为->路径长度乘经过路径次数的和。

求经过次数：设这条边两端的点，被经过的次数分别为A和B，那么这条边被经过的次数就是A*B，它对总距离和的贡献就是(A*B*此边长度)。

每条边两端点经过次数的计算，可以用一次dfs解决。

任取一点为根，在dfs的过程中，对每个点k记录其子树包含的点数（包括其自身），设点数为sum[k]，则k的父亲一侧的点数即为N-sum[k]。这个统计可以和遍历同时进行。故时间复杂度为O(n)。

HDU2376：求完距离和，再除以总路径数N*(N-1)/2，即为最后所求

HDU6446：根据插点排序的思路，再乘以（N-1）! * 2，即为最后所求

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 int sum[maxn], n;

 ll dp[maxn];

 struct Edge

 {

     int v, w;

     Edge(int _v = , int _w = )

     {

         v = _v;

         w = _w;

     }

 };

 vector<Edge> tree[maxn];

 void dfs(int cur, int father)

 {

     sum[cur] = ;

     for(int i = ; i < tree[cur].size(); i++)

     {

         int son = tree[cur][i].v;

         ll len = tree[cur][i].w;

         if(father == son)

             continue;

         dfs(son, cur);

         sum[cur] += sum[son];

         dp[cur] += dp[son] + (n-sum[son]) * sum[son] * len;

     }

 }

 int main()

 {

     int u, v, w, T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d", &n);

         for(int i = ; i < n; i++)

             tree[i].clear();

         memset(sum, , sizeof(sum));

         memset(dp, , sizeof(dp));

         for(int i = ; i < n-; i++)

         {

             scanf("%d%d%d", &u, &v, &w);

             tree[u].push_back(Edge(v,w));

             tree[v].push_back(Edge(u,w));

         }

         dfs(, -); //设0为根节点

         printf("%I64d\n", dp[]); //这里输出的是距离和

     }

     return ;

 }

巴特西

树形DP--求树上任意两点间距离和

最新文章

热门文章