记录编号	488698	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[WC 2018] 通道	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	88.824 s
提交时间	2018-02-23 17:03:09	内存使用	6.03 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>
#define ll long long
using namespace std;

const int MAXN = 100010;
int N;
vector<int> G[3][MAXN];
vector<ll> D[3][MAXN];

inline int myrand(int l, int r) {
    r++; //[l, r)
    while(r - l > 1) {
        int m = (l + r) / 2;
        if(rand() & 1) l = m; else r = m;
    }
    return l;
}

int id;
ll dist[MAXN];
void dfs(int u, int f, ll d) {
    int i, v;
    dist[u] += d;
    for(i = 0; i < G[id][u].size(); i++) if((v = G[id][u][i]) != f) 
        dfs(v, u, d + D[id][u][i]);
}

int main() {
    freopen("tunnel.in", "rt", stdin);
	freopen("tunnel.out", "wt", stdout);

    clock_t end = clock() + CLOCKS_PER_SEC * 3.60;

    int i, k, u, v; ll d;
    scanf("%d", &N);
    for(k = 0; k < 3; k++) for(i = 1; i < N; i++) {
        scanf("%d%d%lld", &u, &v, &d);
        G[k][u].push_back(v), D[k][u].push_back(d);
        G[k][v].push_back(u), D[k][v].push_back(d);
    }

    ll Ans = 0;
    while(clock() < end) {
        u = myrand(1, N); //random start
        for(k = 1; k <= 7; k++) { //iterate
            memset(dist, 0, sizeof(ll) * (N + 1));
            for(id = 0; id < 3; id++) dfs(u, 0, 0);

            ll maxd = 0; int maxp = u;
            for(i = 1; i <= N; i++) if(dist[i] > maxd) maxd = dist[i], maxp = i;
            u = maxp;
            Ans = max(Ans, maxd);
        }
    }
    printf("%lld", Ans);
}