记录编号	285380	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	ljt	是否通过	通过
代码语言	C++	运行时间	0.379 s
提交时间	2016-07-22 12:16:26	内存使用	8.13 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct p {
        int to, next;
}edge[400005], dxedge[200005];
int head[200005],dxhead[200005], top = 0, dxtop = 0;
long long rank[200005];
bool did[200005];
int n;
long long maxx = 0;

void push(int from, int to)
{
        edge[++top].to = to;
        edge[top].next = head[from];
        head[from] = top;
}

void pushdx(int from, int to)
{
        dxedge[++dxtop].to = to;
        dxedge[dxtop].next = dxhead[from];
        dxhead[from] = dxtop;
}

void dfsdx(int i )
{
        for (int k = head[i]; k; k = edge[k].next) {
                int nd = edge[k].to;
                if (!did[nd]) {
                        did[nd] = true;
                        pushdx(i, nd);
                        dfsdx(nd);
                }
        }
}

long long dfs(int i) {
        long long ans = 0, sigma = 0;
        long long max1 = 0, max2 = 0;
        for (int k = dxhead[i]; k; k = dxedge[k].next) {
                int nd = dxedge[k].to;
                sigma = (sigma+rank[nd])%10007;
                if (rank[nd] >= rank[max1]) {
                        max2 = max1;
                        max1 = nd;
                } else if (rank[nd] > rank[max2])
                        max2 = nd;
        }
        maxx = max(maxx, rank[max1]*rank[max2]);
        for (int k = dxhead[i]; k; k = dxedge[k].next) {
                int nd = dxedge[k].to;
                ans = (ans+rank[nd]*((sigma-rank[nd])+10007))%10007;
        }
        //////////第一种：兄弟之间
        for (int k = dxhead[i]; k; k = dxedge[k].next) {
                int nk = dxedge[k].to;
                for (int j = dxhead[nk]; j; j = dxedge[j].next) {
                        int nd = dxedge[j].to;
                        ans = (ans+rank[i]*rank[nd]*2)%10007;
                        maxx = max(maxx,rank[i]*rank[nd]);
                }
        }
        for (int k = dxhead[i]; k; k = dxedge[k].next) {
                int nd = dxedge[k].to;
                ans = (ans + dfs(nd))%10007;
        }
        //cout << i << " " << ans << endl;
        return ans;
}

int main()
{
        freopen("linkb.in", "r", stdin);
        freopen("linkb.out", "w", stdout);
        memset(head,0,sizeof head);
        memset(dxhead,0,sizeof dxhead);
        memset(rank, 0, sizeof rank);
        scanf("%d", &n);
        for (int i = 1; i < n; i++) {
                int a, b;
                scanf("%d %d", &a, &b);
                push(a, b);
                push(b, a);
                did[i] = false;
        }
        for (int i = 1; i <= n; i++)
                scanf("%d", &rank[i]);
        did[1] = 1;
        dfsdx(1);
        long long res = dfs(1)%10007;
        cout << maxx << " " << res <<endl;
        return 0;
}