题意
树上每个结点的权值为\(w_i\),若点\(i\)和点\(j\)满足:\(i\)和\(j\)的最短距离为2,则会产生$ w_i * w_j $的联合权值。
求最大联合权值和联合权值之和。
分析
①最大联合权值
对于结点\(u\),\(u\)的叶节点之间一定能产生联合权值。
那么与\(u\)相连的所有点之间都能产生联合权值。
\(u\)的最大联合权值就是所有相连点中的最大值*次大值。
总的最大联合权值就是所有结点最大联合权值的最大值。
②联合权值之和
点集\(1,2,...,k\)产生的联合权值之和为:
\[2\sum_{i,j=1}^kw_{i}w_{j}(i\ne j) \]\[=(\sum_{i=1}^k w_{i})^2-\sum_{i=1}^k w_{i}^2 \]只需维护和与平方和即可。
代码
#include<iostream>
#include<cstdio>
const int maxn = 200000 + 10;
const int mod = 10007;
int nxt[maxn << 1], to[maxn << 1], head[maxn << 1], val[maxn << 1], cnt;
int max1[maxn << 1], max2[maxn << 1];//最大值及次大值
int sum[maxn << 1], sum2[maxn << 1];//和及平方和
int Max, Sum;//最大联合权值
int n, x, y;
inline void add(int a, int b) {
to[++cnt] = b;
nxt[cnt] = head[a];
head[a] = cnt;
}
inline void dfs1(int u, int fa) {
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
sum[u] = (sum[u] + val[v]) % mod;
sum2[u] = (sum2[u] + (val[v] * val[v] % mod)) % mod;
if (v == fa) continue;
dfs1(v, u);
}
}
inline void dfs2(int u, int fa) {
max1[u] = val[fa];
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) continue;
if (val[v] >= max1[u]) max2[u] = max1[u], max1[u] = val[v];
if (val[v] < max1[u]) {
if (val[v] > max2[u]) max2[u] = val[v];
}
dfs2(v, u);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++) {
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++) {
Sum = (Sum + (sum[i] * sum[i] - sum2[i]) % mod) % mod;
Max = std::max(Max, (max1[i] * max2[i]));
}
printf("%d %d", Max, Sum);
return 0;
}
标签:NOIP2014,val,int,max1,dfs,max2,联合,权值
From: https://www.cnblogs.com/MrWangnacl/p/16810589.html