专栏文章

P1351 题解

aalbertting
P1351题解参与者 8已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@miqmjwqv
此快照首次捕获于
2025/12/04 07:14
3 个月前
此快照最后确认于
2025/12/04 07:14
3 个月前
查看原文
楼上大佬的淀粉质小蒟蒻不会（哭）。
那就来一篇十分简短（但是不易懂？）的题解吧！

推式子

首先我们可以发现，这张图有 NN 个节点和 N−1N - 1，所以这张图实际上是一棵无根树，两点之间有唯一路径。
对于每一对 (u,v)(u, v)，必然会有一点（就叫 kk 吧）在这两点之间。
所以对于每一个点 kk，可产生联合权值：
∑i=1m∑j=1mwiwj\sum\limits_{i=1}^m\sum\limits_{j=1}^m{w_i}{w_j}
（mm 是与 kk 相邻的点的个数）
化简亿下：
∑i=1m∑j=1mwiwj=∑i=1m(wi∑j=1mwj)=(∑i=1mwi)(∑j=1mwj)=(∑i=1mwi)2\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=vu = v。
辣么，把多算的减掉就好了！
式子变成：
(∑i=1mwi)2−(∑i=1mwi2)(\sum\limits_{i=1}^m{w_i})^2-(\sum\limits_{i=1}^m{w_i^2})
把所有的 kk 遍历一遍加起来，式子变成：
∑k=1n((∑i=1mkwi)2−(∑i=1mkwi2))\sum\limits_{k=1}^n((\sum\limits_{i=1}^{m_k}{w_i})^2-(\sum\limits_{i=1}^{m_k}{w_i^2}))
大功告成！
哦对，还有 最大值！
对于每个 kk，找一下与之相连的最大的 wuw_u 和 wvw_v 乘一下再和 ans 比个大小就好了！

Code!

CPP
#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__
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...