M_sea

洛谷2052 道路修建
Luogu算法Dfs算出每个节点的子节点数,然后顺便统计答案。统计答案的话,可以这么想:断掉查询的边树就分裂成了两...
扫描右侧二维码阅读全文
16
2017/11

洛谷2052 道路修建

Luogu

算法

Dfs算出每个节点的子节点数,然后顺便统计答案。

统计答案的话,可以这么想:

断掉查询的边树就分裂成了两部分,一部分是v的子节点数,剩下的是n-v的子节点数。
那么减一下就变成了n-v的子节点数*2。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
typedef long long LL;
inline LL read() {
    LL X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
struct Edge { LL v,w,nxt; } e[2000010];
LL head[1000010],cnt;
inline void addEdge(LL u,LL v,LL w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
LL down[1000010];
bool vis[1000010];
LL n,ans=0;
inline void Dfs(LL u) {
    vis[u]=true; down[u]=1;
    for (re LL i=head[u];i;i=e[i].nxt) {
        LL v=e[i].v;
        if (vis[v]) continue;
        Dfs(v); down[u]+=down[v];
        ans+=abs(n-down[v]*2)*e[i].w;
    }
}
int main() {
    n=read();
    for (re LL i=1;i<n;i++) {
        LL u=read(),v=read(),w=read();
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    Dfs(1); printf("%lld\n",ans);
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 39 PM

发表评论