首页 技术 正文
技术 2022年11月23日
0 收藏 495 点赞 3,077 浏览 782 个字

传送门

假设数据再大些,我这就是正解,然而题解里总是各种水过。

两边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 ;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102