Skip to content

14056: 【原4056】首都

题目

题目描述

author: BowenTan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4056

Description

现在，你成为了元首。

你的国家，是一棵树，一棵有n(n <= 200000)个点的树，每个点是一个城市。

每条边有一个运输容量限制。 两个城市之间的运输强度定义为两个点在树中路径上容量最小的那条边的容量。

你想指ying定dian一个首都，当然，还是要讲点基本法： 每个点的承受度定义为这个点与其他所有点运输强度之和，首都的承受度是最大的。

现在有个记者问你首都的承受度是多少，你不能无可奉告。

input format

本题包含多组输入数据，数据开始首先输入数据组数T(T <= 3)。

每组数据的第一行包含一个数n(n <= 200000)，意义如题目描述。

之后n - 1行都包含三个数u, v, w(0 < w <= 10^6)，分别表示一条边的两个端点和容量。

output format

对于每一组输入，都输出首都的承受度。

sample input

2
4
1 2 2
2 4 1
2 3 1
4
1 2 1
2 4 1
2 3 1

sample output

4
3

limits

  • 对于20%的数据，n <= 1000
  • 对于100%的数据，n <= 200000

zqy2018's solution 

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4056.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
pair<int, pair<int, int> > e[200005];
int n, l[400005], r[400005];
ll tag[400005], maxi;
int fa[400005], siz[400005], tot;
int Find(int x){
    return (fa[x] == x ? x: (fa[x] = Find(fa[x])));
}
void Union(int x, int y, int w){
    x = Find(x), y = Find(y);
    ++tot;
    fa[x] = fa[y] = tot, fa[tot] = tot;
    l[tot] = x, r[tot] = y;
    tag[x] += 1ll * siz[y] * w;
    tag[y] += 1ll * siz[x] * w;
    siz[tot] = siz[x] + siz[y];
}
void dfs(int cur, ll tg){
    tg += tag[cur];
    maxi = max(maxi, tg);
    if (cur > n) 
        dfs(l[cur], tg), dfs(r[cur], tg);
}
void init(){
    n = read();
    REP(i, 1, n - 1){
        e[i].second.first = read();
        e[i].second.second = read();
        e[i].first = read();
        fa[i] = i, siz[i] = 1;
    }
    fa[n] = n, siz[n] = 1;
    memset(tag, 0, sizeof(tag));
    sort(e + 1, e + n);
}
void solve(){
    tot = n;
    REPR(i, n - 1, 1){
        int w = e[i].first;
        int u = e[i].second.first, v = e[i].second.second;
        Union(u, v, w);
    }
    int rt = Find(1);
    maxi = 0;
    dfs(rt, 0);
    printf("%lld\n", maxi);
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}