描述 Description
众所周知，moreD 的宠物已经被 moreD 奴役得体无完肤。这只宠物实在忍无可忍，把自己每天走魔法树的经历告诉了自己的宠物。同时他还说明了自己爬树是多么地慢，以至于 moreD 每天都残酷地训练他爬树。
幸运的是 moreD 的宠物的宠物不是 moreD 的宠物，moreD 的宠物深知” 宠物是用来宠的而不是用来奴役的” 这一点，所以 moreD 的宠物对待自己的宠物很有爱。所以 moreD 的宠物与其宠物商量着要推翻 moreD 的暴政，方法是把 moreD 告上法庭，就以自己每天被迫爬树来做证据。
由于魔法树是树，训练树当然也是树啦。
moreD 的训练有着 GX 的文化，每天 moreD 会把自己的宠物通灵到树的一个端点上，这个通灵点可能与之前的通灵点相同。然后 moreD 命令他的宠物从这个点开始走，让这只宠物随便访问自己该天之前没有访问过的节点，一直走到该天无路可走，训练才会结束，宠物才可以休息。
moreD 的宠物每天都会在这棵树上训练，幸运的是他每天走过的训练路径都不同，直到若干天后，所有可能的训练路径都被走遍了。
你，作为 moreD 宠物的宠物，一只被 moreD 的宠物宠着的宠物，当然想帮 moreD 的宠物算出他总共走过的路径长度啦。
输入格式 InputFormat
第一行包含两个正整数 N,M，表示树的点数与边数。
接下来 M 行，每行三个正整数表示 Li,bi,ci 分别表示树上有一条长度为 Li 的连接 bi,ci 两个结点的边。
输出格式 OutputFormat
仅一行表示答案。
样例输入 SampleInput
5 4
1 2 1
1 3 1
2 4 2
2 5 2
样例输出 SampleOutput
37
代码 Code
我们可以计算每条边会对答案贡献多少次。对每一条边单独考虑。一条边被计算的次数是这条边分开的两棵子树中左边的节点数乘右边的叶子数加上右边的节点数乘左边的叶子数。实现仅需要保存每个子树的叶子数和节点数就可完美解决。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,next,val;
}e[200005];
int head[100005],node[100005],leaf[100005];
ll ans,cnt;
inline void insert(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
void dfs(int s,int fa)
{
int i,j,t;
if (e[head[s]].next==0) leaf[s]=1;
node[s]=1;
for (i=head[s];i;i=e[i].next) if (e[i].to!=fa)
{
dfs(e[i].to,s);
leaf[s]+=leaf[e[i].to];node[s]+=node[e[i].to];
}
}
void dp(int s,int fa)
{
int i,j,t;
for (i=head[s];i;i=e[i].next) if (e[i].to!=fa)
{
t=e[i].to;
dp(t,s);
ans+=(ll)e[i].val*(leaf[1]-leaf[t])*node[t]+(ll)e[i].val*(node[1]-node[t])*leaf[t];
}
}
int main()
{
freopen("senso.in","r",stdin);
freopen("senso.out","w",stdout);
cnt=0;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&z,&x,&y);
insert(x,y,z);
insert(y,x,z);
}
dfs(1,0);
ans=0;
dp(1,0);
printf("%lld\n",ans);
}