联合权值

题目大意:

你有一棵树,问你距离为二的节点的最大联合权值与联合权值和

分析:

找到中间的点, 然后枚举他的儿子们, 求个和, 然后再求个最大值, 好像就完了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 10;
const int mod = 10007;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

ll n, cur, sum, __maxn, w[maxn];
ll head[maxn], __next[maxn << 1], __edge[maxn << 1];

inline void AddEdge(int u, int v) 
{
    __next[++cur] = head[u];
    head[u] = cur;
    __edge[cur] = v;
}

signed main()
{
    n = __read();
    for (int i(1); i < n; ++i) {
        int u = __read(), v = __read();
        AddEdge(u, v), AddEdge(v, u);
    }
    for (int i(1); i <= n; ++i) w[i] = __read();
    for (int i = 1; i <= n; ++i) {
        ll _mx(0), _sum(0);
        for (int p = head[i]; p; p = __next[p]) {
            sum += _sum * w[__edge[p]] % mod;
            _sum += w[__edge[p]];
            __maxn = max(__maxn, _mx * w[__edge[p]]);
            _mx = max(_mx, w[__edge[p]]);
        }
    }
    printf ("%lld %lld\n", __maxn, sum * 2 % mod);
    system("pause");
}