1、题面
2、总结
第一次回忆一下当年的题目。但是这道题已经做烂了，只是看还记得树遍历会写么。
然后我写了一下，有点费劲，交上去之后只有70，比较尴尬，看了下去年5月写的代码，发现完全不是一个感觉啊。。。什么鬼？为什么那个时候写得那么长啊。难道是我现在想错了什么？
结果我发现当年我交过一个70分的。。发现差别就在于有没有开long long。
SHIT。想了一上午。
3、代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define MAXN 200005
#define MOD 10007 #ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif typedef long long ll; ll h[MAXN], w[MAXN], tot[MAXN], n, u, v, o, ans, maxv; struct edge {
ll v, next;
} e[MAXN * ]; void add(ll u, ll v) {
o++, e[o] = (edge) {v, h[u]}, h[u] = o;
} void work(ll x, ll fa) {
ll sonv = , tmax = , vmax;
for (ll o = h[x]; o; o = e[o].next) {
ll v = e[o].v;
sonv += w[v];
if (tmax < w[v]) tmax = w[v], vmax = v;
}
for (ll o = h[x]; o; o = e[o].next) {
ll v = e[o].v;
if (v == fa) continue;
if (v != vmax) maxv = max(maxv, tmax * w[v]);
tot[v] += w[fa] + sonv - w[v], work(v, x);
maxv = max(maxv, w[v] * w[fa]);
}
} int main() {
freopen("link.in", "r", stdin);
freopen("link.out", "w", stdout);
scanf(LL, &n);
for (ll i = ; i < n; i++) scanf(LL " " LL, &u, &v), add(u, v), add(v, u);
for (ll i = ; i <= n; i++) scanf(LL, &w[i]);
work(, );
for (ll i = ; i <= n; i++) (ans += w[i] * tot[i]) %= MOD;
printf(LL " " LL, maxv, ans);
return ;
}
风格也差别比较大。