2435: [Noi2011]道路修建(树上操作)

时间:2022-01-10 22:04:15

2435: [Noi2011]道路修建

题目:传送门


题解:

   建完边之后以1为根建树,统计深度和各个点的子树大小(包括自己)

   询问的时候:答案=长度*abs(n-深度大的点的子树大小*2)

   ans+=a[i].c*abs(n-tot[y]*2)


代码:

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
struct node
{
int x,y,c,next;
}a[];int len,last[];
int n,tot[],dep[];
void ins(int x,int y,int c)
{
len++;a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
}
void dfs(int x,int fa)
{
tot[x]=;dep[x]=dep[fa]+;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa)
{
dfs(y,x);
tot[x]+=tot[y];
}
}
}
int main()
{
scanf("%d",&n);len=;memset(last,,sizeof(last));
for(int i=;i<n;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
dfs(,);
LL ans=;
for(int i=;i<=len;i+=)
{
int x=a[i].x,y=a[i].y;
if(dep[x]>dep[y])swap(x,y);
ans+=LL(a[i].c)*abs(n-tot[y]*);
}
printf("%lld\n",ans);
return ;
}