「题解」Luogu 1351「联合权值」

分析

按照LCA的思想就可以得到以下做法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<vector>
#include<algorithm>
typedef long long int64;
const int MAXN = 200000 + 6,MOD = 10007,INF = 0x3f3f3f3f;
int64 W[MAXN];
std::vector<int> G[MAXN];
inline void addEdge(int u,int v){G[u].push_back(v);}
int main(){
int n,u,v;scanf("%d",&n);
int64 delta,delta1,delta2,max = -INF,sum = 0;
for(int i = 1;i < n;i++){
scanf("%d %d",&u,&v);
addEdge(u,v),addEdge(v,u);
}
for(int i = 1;i <= n;i++) scanf("%lld",&W[i]);
for(int i = 1;i <= n;i++){
delta2 = delta1 = 0;
for(int j = 0;j < G[i].size();j++){
delta = W[G[i][j]] * delta2;
max = std::max(max,W[G[i][j]] * delta1);
delta1 = std::max(delta1,W[G[i][j]]);
sum += delta % MOD;
sum %= MOD;
delta2 += W[G[i][j]];
}
}
printf("%lld %lld",max,sum * 2 % MOD);

return 0;
}
分享到