[RT][NOIP2015]联合权值

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 ;
 }

风格也差别比较大。