假设数据再大些,我这就是正解,然而题解里总是各种水过。
两边dfs,一遍求重心,一遍统计距离。
——代码
#include <cstdio>
#include <cstring>
#define MAXN 1001 using namespace std; int n, cnt, tot, ans, sum;
int head[MAXN], next[MAXN], to[MAXN], val[MAXN], size[MAXN], dis[MAXN], f[MAXN]; inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void dfs(int u)
{
int i, v;
size[u] += val[u];
for(i = head[u]; i != -; i = next[i])
{
v = to[i];
if(v != f[u])
{
f[v] = u;
dfs(v);
size[u] += size[v];
}
}
if( * size[u] >= tot && !ans) ans = u;
} inline void dfs1(int u)
{
int i, v;
sum += (dis[u] - ) * val[u];
for(i = head[u]; i != -; i = next[i])
{
v = to[i];
if(!dis[v])
{
dis[v] = dis[u] + ;
dfs1(v);
}
}
} int main()
{
int i, x, y;
scanf("%d", &n);
memset(head, -, sizeof(head));
for(i = ; i <= n; i++)
{
scanf("%d %d %d", &val[i], &x, &y);
if(x) add(i, x), add(x, i);
if(y) add(i, y), add(y, i);
tot += val[i];
}
dfs();
dis[ans] = ;
dfs1(ans);
printf("%d", sum);
return ;
}