360免费做网站电话,seo顾问多少钱,响应式网站算几个页面,推荐自助建网站平台【题目来源】https://www.acwing.com/problem/content/513/【题目描述】无向连通图 G 有 n 个点#xff0c;n−1 条边。 点从 1 到 n 依次编号#xff0c;编号为 i 的点的权值为 Wi#xff0c;每条边的长度均为 1。 图上两点 (u,v) 的距离定义为 u 点到 v 点的最短距离。 对…【题目来源】https://www.acwing.com/problem/content/513/【题目描述】无向连通图 G 有 n 个点n−1 条边。 点从 1 到 n 依次编号编号为 i 的点的权值为 Wi每条边的长度均为 1。 图上两点 (u,v) 的距离定义为 u 点到 v 点的最短距离。 对于图 G 上的点对 (u,v)若它们的距离为 2则它们之间会产生 Wu×Wv 的联合权值。 请问图 G 上所有可产生联合权值的有序点对中联合权值最大的是多少所有联合权值之和是多少【输入格式】 第一行包含 1 个整数 n。 接下来 n−1 行每行包含 2 个用空格隔开的正整数 u、v表示编号为 u 和编号为 v 的点之间有边相连。 最后 1 行包含 n 个正整数每两个正整数之间用一个空格隔开其中第 i 个整数表示图 G 上编号为 i 的点的权值为 Wi。【输出格式】 输出共 1 行包含 2 个整数之间用一个空格隔开依次为图 G 上联合权值的最大值和所有联合权值之和。 由于所有联合权值之和可能很大输出它时要对 10007 取余。【数据范围】 1n≤200000, 0Wi≤10000【输入样例】 5 1 2 2 3 3 4 4 5 1 5 2 3 10【输出样例】 20 74【算法分析】 本例代码采用链式前向星存无向图并基于此进行无向图的深度优先搜索。详见https://blog.csdn.net/hnjzsyjyj/article/details/119917795 链式前向星的相关介绍可参考https://blog.csdn.net/hnjzsyjyj/article/details/119917795https://blog.csdn.net/hnjzsyjyj/article/details/127190456https://blog.csdn.net/hnjzsyjyj/article/details/126474608【算法代码】 代码来源于https://www.acwing.com/solution/content/3516/
/* 链式前向星存图
val[idx] 表示第 idx 条边的权值。
e[idx] 表示第 idx 条边的终点。
ne[idx] 表示与第 idx 条边同起点的最近一次被添加的边的编号。
h[a] 表示以结点 a 为起点的最近一次被添加的边的编号。这个表述是在使用 ne[idx]h[a] 时也即使用 h[a]idx 更新 h[a] 之前而言的。要特别注意这个语境。
*/#include bits/stdc.h
using namespace std;const int N2e55;
const int MN1;
const int mod10007;int n;
int h[N],e[M],ne[M],idx;
int w[N];
int f[N],g[N];
int imax, isum;void add(int a,int b) {e[idx]b,ne[idx]h[a],h[a]idx;
}void dfs(int u, int father) {int sum0, maxv0;for(int ih[u]; ~i; ine[i]) { //~i; equivalent to i!-1;int je[i];if(j!father) {dfs(j,u);imaxmax(imax,w[u]*f[j]);imaxmax(imax,maxv*w[j]);maxvmax(maxv,w[j]);isum(isumw[u]*g[j])%mod;isum(isumsum*w[j])%mod;sum(sumw[j])%mod;f[u]max(f[u],w[j]);g[u](g[u]w[j])%mod;}}
}int main() {scanf(%d,n);memset(h,-1,sizeof(h));for(int i0; in-1; i) {int a,b;scanf(%d %d,a,b);add(a,b),add(b,a);}for(int i1; in; i) scanf(%d,w[i]);dfs(1,-1);printf(%d %d\n,imax,2*isum%mod);return 0;
}/*
in:
5
1 2
2 3
3 4
4 5
1 5 2 3 10out:
20 74
*/【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/119917795https://www.acwing.com/solution/content/3516/https://blog.csdn.net/hnjzsyjyj/article/details/127190456https://blog.csdn.net/hnjzsyjyj/article/details/126474608
