联合权值
题目大意
给你一个图,有\(n-1\)条边,距离均为\(1\),每距离为\(2\)的两个点的联合权值为\(W_u \times W_v\),求联合权值的最大值和联合权值总和。
solution
70pts
这道题稍微看一下就想到可以枚举一个点,然后对于每个点所相连的点到另一个所相连的点的距离一定为\(2\),所以我们就可以暴力枚举这一个点,然后进行加和。这样我们就得到了70分的做法。
// 70pts
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int n;
const int mod = 10007;
struct edge {
int next,to;
} e[400000];
int head[400001],tot,val[200001],maxn=-0x7fffffff,ans,fa[200001];
void add(int x,int y) {
e[++tot].next = head[x];
head[x] = tot;
e[tot].to = y;
}
void dfs_bgn(int x,int f) {
fa[x]=f;
for(int i=head[x]; i; i=e[i].next) {
int v=e[i].to;
if(v!=f)
dfs_bgn(v,x);
}
return ;
}
void dfs(int x) {
for(int i=head[x]; i; i=e[i].next) {
int v=e[i].to;
if(v!=fa[x]) {
int k=fa[x];
if(k!=0) {
ans+=((val[k]%mod)*(val[v]%mod))%mod;
ans%=mod;
ans+=((val[k]%mod)*(val[v]%mod))%mod;
ans%=mod;
maxn=max(maxn,val[k]*val[v]);
}
dfs(v);
}
}
for(int i=head[x]; i; i=e[i].next)
for(int j=head[x]; j; j=e[j].next) {
int k=e[i].to,v=e[j].to;
if(k!=v && k!=fa[x] && v!=fa[x]) {
ans+=((val[k]%mod)*(val[v]%mod))%mod;
ans%=mod;
maxn=max(maxn,val[k]*val[v]);
}
}
}
int main() {
scanf("%d",&n);
for(int i=1; i<n; i++) {
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1; i<=n; i++)scanf("%d",&val[i]);
dfs_bgn(1,0);
dfs(1);
printf("%d %d",maxn,ans);
return 0;
}
100pts
因为现在没考试,所以思想比较懈怠,就没有相处100pts的做法。
100pts的做法就是加了一步小优化,将我的n方枚举转变为线性。
线性做法是这样的,枚举到一个点,那么它的一个相邻点必定会乘以其他的点,所以这就是一个乘法分配律。
既然这样,我们就好说了。我们求出每个点相邻点的总和,然后再根据乘法分配律对答案进行更新。
那么最大值怎么办呢?最大值的话可以仔细想想,因为最大值就是一个点所相连的最大乘以次大,所以我们再枚举这个点周边点的时候维护一下就行了。
//100pts
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int n;
const long long mod = 10007;
struct edge {
int next,to;
} e[400000];
int head[400001],tot,fa[200001];
long long val[200001],maxn=-0x7fffffff,ans;
void add(int x,int y) {
e[++tot].next = head[x];
head[x] = tot;
e[tot].to = y;
}
void dfs_bgn(int x,int f) {
fa[x]=f;
for(int i=head[x]; i; i=e[i].next) {
int v=e[i].to;
if(v!=f)
dfs_bgn(v,x);
}
return;
}
void dfs(int x) {
long long max1=0,max2=0,sum=0;
for(int i=head[x]; i; i=e[i].next) {
int v=e[i].to;
if(v!=fa[x]) dfs(v);
if(max1<val[v])max2=max1,max1=val[v];
else if(max1==val[v])max2=max1;
else if(max1>val[v] && max2<val[v]) max2=val[v];
sum+=val[v];
}
maxn=max(maxn,max1*max2);
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
ans=(ans+(val[v]%mod)*(sum-val[v]%mod))%mod;
ans%=mod;
}
}
int main() {
scanf("%d",&n);
for(int i=1; i<n; i++) {
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1; i<=n; i++)scanf("%lld",&val[i]),val[i]%=mod;
dfs_bgn(1,0);
dfs(1);
printf("%lld %lld",maxn,ans);
return 0;
}