问题描述
无向连通图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 取余。
输入样例
5
12
23
34
45
15 23 10输出样例
20 74样例说明
本例输入的图如上所示，距离为2的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、
(4,2)、(5,3)。其联合权值分别为2、15、2、20、15、20。其中最大的是20，
总和为74。
数据范围及提示
对于30%的数据，1<n≤100；
对于60%的数据，1<n≤2000；
对于100%的数据，1<n≤200000，0<Wi≤10000。
题解和代码
很显然这道题用广搜一遍求就可以了。
#include <cstdio>
#include <deque>
#include <vector>
using namespace std;
struct edge_type
{
int u, v, nextu, nextv;
};
struct deque_type
{
int data[200005], h, t;
deque_type()
{
h = 0;
t = 1;
}
void push_back(int key)
{
data[t++] = key;
}
int front()
{
return data[h];
}
void pop_front()
{
++h;
}
bool empty()
{
return h >= t;
}
};
deque_type q;
vector<int> vec;
int w[200005], hu[200005], hv[200005], deep[200005], fa[200005], n;
bool vis[200005];
edge_type edge[200005];
int main()
{
scanf("%d", &n);
int u, v;
for (int i = 1; i < n; ++i)
{
scanf("%d%d", &u, &v);
edge[i].u = u;
edge[i].v = v;
edge[i].nextu = hu[u];
edge[i].nextv = hv[v];
hu[u] = i;
hv[v] = i;
}
for (int i = 1; i <= n; ++i)
scanf("%d", w + i);
deep[1] = 1;
fa[1] = 0;
vis[1] = true;
q.push_back(1);
int now, k, p, nowpos;
int maxx = 0, summ = 0, value, nowsum, tmp, nowmax;
while (!q.empty())
{
now = q.front();
nowsum = 0;
nowmax = 0;
q.pop_front();
nowpos = q.t;
k = hu[now];
if(deep[now] > 2)
{
value = w[now] * w[fa[fa[now]]];
if (maxx < value) maxx = value;
summ += value;
summ %= 10007;
}
while (k)
{
p = edge[k].v;
if (!vis[p])
{
tmp = (nowsum % 10007) * (w[p] % 10007);
summ += tmp;
summ %= 10007;
tmp = nowmax * w[p];
if (tmp > maxx) maxx = tmp;
q.push_back(p);
nowsum += w[p];
nowsum %= 10007;
if(nowmax < w[p]) nowmax = w[p];
vis[p] = true;
deep[p] = deep[now] + 1;
vec.push_back(p);
fa[p] = now;
}
k = edge[k].nextu;
}
k = hv[now];
while (k)
{
p = edge[k].u;
if (!vis[p])
{
tmp = (nowsum % 10007) * (w[p] % 10007);
summ += tmp;
summ %= 10007;
tmp = nowmax * w[p];
if (tmp > maxx) maxx = tmp;
q.push_back(p);
nowsum += w[p];
nowsum %= 10007;
if(nowmax < w[p]) nowmax = w[p];
vis[p] = true;
deep[p] = deep[now] + 1;
vec.push_back(p);
fa[p] = now;
}
k = edge[k].nextv;
}
}
summ = (summ + summ) % 10007;
printf("%d %d\n", maxx, summ);
}