P1351 题解

· · 题解

楼上大佬的淀粉质小蒟蒻不会（哭）。

那就来一篇十分简短（但是不易懂？）的题解吧！

推式子

首先我们可以发现，这张图有 N 个节点和 N - 1，所以这张图实际上是一棵无根树，两点之间有唯一路径。

对于每一对 (u, v)，必然会有一点（就叫 k 吧）在这两点之间。

所以对于每一个点 k，可产生联合权值：

\sum\limits_{i=1}^m\sum\limits_{j=1}^m{w_i}{w_j}

（m 是与 k 相邻的点的个数）

化简亿下：

\begin{aligned} \sum\limits_{i=1}^m\sum\limits_{j=1}^m{w_i}{w_j} &=\sum\limits_{i=1}^m({w_i\sum\limits_{j=1}^m}{w_j}) \newline &=(\sum\limits_{i=1}^m{w_i})(\sum\limits_{j=1}^m{w_j}) \newline &=(\sum\limits_{i=1}^m{w_i})^2 \end{aligned}

Clever OIer 肯定都看出来了：

照这么算，肯定会出现 u = v。

辣么，把多算的减掉就好了！

式子变成：

(\sum\limits_{i=1}^m{w_i})^2-(\sum\limits_{i=1}^m{w_i^2})

把所有的 k 遍历一遍加起来，式子变成：

\sum\limits_{k=1}^n((\sum\limits_{i=1}^{m_k}{w_i})^2-(\sum\limits_{i=1}^{m_k}{w_i^2}))

大功告成！

哦对，还有 最大值！

对于每个 k，找一下与之相连的最大的 w_u 和 w_v 乘一下再和 ans 比个大小就好了！

Code!

#include <bits/stdc++.h>
#define __Made return
#define in 0
#define China__ ;
using namespace std;

int n;
int u, v;
vector<int> mp[200005];
long long w[200005];
long long ans1, ans2;

void solve(int x)
{
    long long max1 = 0, max2 = 0;
    long long sum1 = 0, sum2 = 0;
    for(auto i : mp[x])
    {
        if(w[i] >= max1) max2 = max1, max1 = w[i];
        else if(w[i] >= max2) max2 = w[i];
        sum1 += w[i];
        sum2 += w[i] * w[i];
    }
    ans1 = max(ans1, max1 * max2);
    ans2 += sum1 * sum1 - sum2;
    ans2 %= 10007;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n - 1; i++)
    {
        scanf("%d %d", &u, &v);
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    for(int i = 1; i <= n; i++)
        scanf("%lld", &w[i]);
    for(int i = 1; i <= n; i++)
        solve(i);
    printf("%lld %lld", ans1, ans2);
    __Made in China__
}