分析

由于本题要求联合权值之间的Dist为2
他们之间刚好夹着一个点
为了处理方便，我们肯定是直接枚举中间夹着的点
那么，我们来考虑需要求的两个东西Max（最大联合权值）和Ans（联合权值之和）

Max：
对于一个点来说，以他为中心点的联合权值最大值一定是与他相连的最大值和次大值之积
所以对于最大值我们就解决了

$\\$

Ans：
那么对于和，我们考虑每个点为中心的所有点的贡献
设每个点权值为 $a_1,a_2,a_3, \cdots ,a_m$
那么总贡献为

$(a_1 \times a_2 + a_1 \times a_3 + \cdots a_1 \times a_m) + (a_2 \times a_3 + a_2 \times a_4 + \cdots a_2 \times a_m) + \cdots (a_{m-1} \times a_m) \\ \Rightarrow \sum_{i=1}^{m-1} \sum_{j=i+1}^{m} a_j \times a_j$

所以可得对于每个点贡献为

$(\sum_{i=1}^{m} a_i)^2 - \sum_{i=1}^{m} a_i^2$

所以我们可以预处理出每个点的 $\sum a_i$ , $\sum a_i^2$ 即可

综合上边两个处理，即可快速得到答案
时间复杂度： $O(n)$

分析

//P1351
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define INF 0x3f3f3f3f
#define Mod 10007
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const int MaxN=2e5+10;

int Total,u,v,w;
int Num[MaxN],Fir[MaxN],Sec[MaxN];
int Sum_one[MaxN],Sum_two[MaxN];
int Next[MaxN<<1],End[MaxN<<1],Head[MaxN],Cur;
int Max,Ans;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Add_Edge(int From,int To) {
    Next[++Cur]=Head[From];
    Head[From]=Cur;
    End[Cur]=To;

}

inline void DFS_one(int New,int Pre) {
    Fir[New]=Num[Pre];
    (Sum_one[New]+=Num[Pre])%=Mod;
    (Sum_two[New]+=Num[Pre]*Num[Pre]%Mod)%=Mod;
    for(int i=Head[New];i;i=Next[i]) {
        if(End[i]==Pre) continue;
        DFS_one(End[i],New);
        if(Num[End[i]]>Fir[New]) Sec[New]=Fir[New],Fir[New]=Num[End[i]];
        else if(Num[End[i]]>Sec[New]) Sec[New]=Num[End[i]];
        (Sum_one[New]+=Num[End[i]])%=Mod;
        (Sum_two[New]+=Num[End[i]]*Num[End[i]]%Mod)%=Mod;
    }
}

inline void DFS_two(int New,int Pre) {
    Max=max(Max,Fir[New]*Sec[New]);
    (Ans+=(Sum_one[New]*Sum_one[New]-Sum_two[New]))%=Mod;
    for(int i=Head[New];i;i=Next[i]) {
        if(End[i]==Pre) continue;
        DFS_two(End[i],New);
    }
}

int main() {
    // File();
    cin>>Total;
    FOR(i,1,Total-1) {
        cin>>u>>v;
        Add_Edge(u,v);
        Add_Edge(v,u);
    }
    FOR(i,1,Total) { cin>>Num[i]; }
    DFS_one(1,0);
    DFS_two(1,0);
    cout<<Max<<" "<<Ans%Mod<<endl;
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}