HDU 3534 Tree (经典树形dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3534

题意：

给你一棵树，问你有多少对点的距离等于树的直径。

思路：

dp[i][0]表示在i的子树中离i最远的距离，dp[i][1]是次远距离。 cnt[i][0]则是最远的点的数量，cnt[i][1]表示次远的数量。

up[i]表示以i向上离i最远的距离。 up_cnt[i]表示向上最远的数量。

写的有点麻烦，调试了2小时。。。

 //#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = 2e5 + ;

 int dp[N][];

 int cnt[N][];

 int up[N];

 int cnt_up[N];

 int son[N][];

 vector <P> G[N];

 void dfs1(int u, int p) {

     dp[u][] = dp[u][] = ;

     son[u][] = son[u][] = u;

     cnt[u][] = cnt[u][] = ;

     int tmp = ;

     for(int i = ; i < G[u].size(); ++i) {

         P temp = G[u][i];

         int v = temp.first;

         if(v == p)

             continue;

         dfs1(v, u);

         if(dp[v][] + temp.second > dp[u][]) {

             dp[u][] = dp[u][];

             son[u][] = son[u][];

             cnt[u][] = cnt[u][];

             dp[u][] = dp[v][] + temp.second;

             son[u][] = v;

             cnt[u][] = cnt[v][];

             tmp = cnt[v][];

         } else if(dp[v][] + temp.second == dp[u][]) {

             cnt[u][] += cnt[v][];

             cnt[u][] = cnt[u][] - tmp;

             dp[u][] = dp[u][];

             son[u][] = v;

         } else if(dp[v][] + temp.second > dp[u][]) {

             dp[u][] = dp[v][] + temp.second;

             cnt[u][] = cnt[v][];

             son[u][] = v;

         } else if(dp[v][] + temp.second == dp[u][]) {

             cnt[u][] += cnt[v][];

         }

     }

 }

 void dfs2(int u, int p) {

     for(int i = ; i < G[u].size(); ++i) {

         P temp = G[u][i];

         int v = temp.first;

         if(v == p)

             continue;

         if(dp[u][] == temp.second + dp[v][]) {

             //up[v] = max(up[u], dp[u][0]) + temp.second;

             if(dp[u][] == ) {

                 cnt_up[v] = cnt_up[u];

                 up[v] = up[u] + temp.second;

                 dfs2(v, u);

                 continue;

             }

             if(up[u] > dp[u][]) {

                 up[v] = up[u] + temp.second;

                 cnt_up[v] = cnt_up[u];

             } else if(dp[u][] > up[u]) {

                 up[v] = dp[u][] + temp.second;

                 if(dp[u][] == dp[u][])

                     cnt_up[v] = cnt[u][] - cnt[v][];

                 else

                     cnt_up[v] = cnt[u][];

             } else {

                 if(dp[u][] == dp[u][])

                     cnt_up[v] = cnt[u][] - cnt[v][];

                 else

                     cnt_up[v] = cnt[u][];

                 cnt_up[v] += cnt_up[u];

                 up[v] = dp[u][] + temp.second;

             }

         } else {

             //up[v] = max(up[u], dp[u][1]) + temp.second;

             if(up[u] > dp[u][]) {

                 up[v] = up[u] + temp.second;

                 cnt_up[v] = cnt_up[u];

             } else if(dp[u][] > up[u]) {

                 up[v] = dp[u][] + temp.second;

                 cnt_up[v] = cnt[u][];

             } else {

                 cnt_up[v] = cnt_up[u] + cnt[u][];

                 up[v] = dp[u][] + temp.second;

             }

         }

         dfs2(v, u);

     }

 }

 int main()

 {

     int n, u, v, c;

     while(~scanf("%d", &n)) {

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

             G[i].clear();

         }

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

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

             G[u].push_back(make_pair(v, c));

             G[v].push_back(make_pair(u, c));

         }

         dfs1(, -);

         cnt_up[] = ;

         dfs2(, -);

         int Max = ;

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

             //cout << dp[i][0] << "  -  " << up[i] << endl;

             Max = max(Max, max(dp[i][], up[i]));

         }

         LL ans = ;

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

             if(Max == dp[i][]) {

                 ans += (LL)cnt[i][];

             }

             if(Max == up[i]) {

                 ans += (LL)cnt_up[i];

             }

         }

         printf("%d %lld\n", Max, ans/);

     }

     return ;

 }

巴特西

HDU 3534 Tree (经典树形dp)

最新文章

热门文章