hdu3899 JLUCPC--树形dp（好题）

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=3899​​

题意：

给定n个点，每个点的人数，n-1条边和边权。选取任意一点u，然后让所有人都移动到u点，问最小的移动距离和是多少。

分析：

注意数字比较大，用long long，递归深度较大，用了#pragma comment(linker, "/STACK:102400000,102400000")

另外这题如果暴力解的话，也就是n个dfs求出每个点的ans，每次都需要初始化vis，耗时O(n)，超时。

#define _CRT_SECURE_NO_DEPRECATE 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

typedef long long ll;

struct Node
{
  int v;
  int w;
  Node(int v_,int w_):v(v_),w(w_){}
};

int n;
ll sum;
bool vis[100005];
ll value[100005];
ll dp[100005];
ll ans[100005];
vector<Node> vec[100005];

/* 以1为根，求出每个节点下的总权和，且求出所有点到点1的代价 */
void dfs(int u, int len)
{
  vis[u] = 1;
  for (int i = 0; i < vec[u].size(); i++)
  {
    int v = vec[u][i].v;
    int w = vec[u][i].w;
    if (!vis[v])
    {
      ans[1] += (len + w)*value[v];
      dfs(v, len + w);
      dp[u] += dp[v];
    }
  }
}

/* 求出其余点的代价和，点1已经在dfs求出 */
void dfs2(int u)
{
  vis[u] = 1;
  for (int i = 0; i < vec[u].size(); i++)
  {
    int v = vec[u][i].v;
    int w = vec[u][i].w;
    if (!vis[v])
    {
      ans[v] = ans[u] + (sum - dp[v])*w - dp[v] * w;//画图就可以看出父节点的值和子节点的值的关系
      dfs2(v);
    }
  }
}

int main() 
{
  while (~scanf("%d", &n))
  {
    sum = 0;
    for (int i = 1; i <= n; i++)
      vec[i].clear();

    for (int i = 1; i <= n; i++)
    {
      scanf("%d", &dp[i]);
      value[i] = dp[i];
      sum += value[i];
    }

    int u, v, w;
    for (int i = 1; i < n; i++)
    {
      scanf("%d%d%d", &u, &v, &w);
      vec[u].push_back(Node(v, w));
      vec[v].push_back(Node(u, w));
    }

    memset(ans, 0, sizeof(ans));
    memset(vis, 0, sizeof(vis));
    dfs(1, 0);
    memset(vis, 0, sizeof(vis));
    dfs2(1);
    ll x = ans[1];
    for (int i = 2; i <= n; i++)
      if (x > ans[i])
        x = ans[i];
    printf("%I64d\n", x);
  }
  return 0;
}