洛谷1351 -- 联合权值

遍历一遍树， 在遍历的同时， 传入节点u的父亲和祖父， 计算答案

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 200010, M = 400100, mod = 10007;

int n;
int h[N], e[M], ne[M], idx;
int w[N];
int res, ans;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa, int gfa)
{
    int mas = 0, maf = 0, sum = 0, squ = 0;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j != fa)
        {
            sum = (sum + w[j]) % mod;
            squ = (squ + w[j] * w[j] % mod) % mod;
            if(w[j] > maf) mas = maf, maf = w[j];
            else if(w[j] > mas) mas = w[j];
            dfs(j, u, fa);
        }
    }
    res = max(res, max(w[u] * w[gfa], mas * maf));
/*

　　　　- - 如果有一组数，我们要求它们除了自己外两两相乘的和，那我们所求的值就等于这组数的和的平方减去它们分别的平方

　　　　2ab=(a+b)^2-a^2-b^2

　　　　2ab+2ac+2bc=(a+b+c)^2-a^2-b^2-c^2

*/

    ans = (ans + (sum * sum % mod - squ + mod) % mod + w[u] * w[gfa] * 2 % mod) % mod;
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    
    for(int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    
    dfs(1, 0, 0);
    
    printf("%d %d\n", res, ans);
    
    
    return 0;
}