[NOIP2014]联合权值

OI 题解

算法：dfs

代码解析：

数据结构

ll v[N];
ll head[N], next[M], to[M], cnt;
ll n;
ll ans, mx;
inline void adde(int x, int y) {
    ++cnt;
    to[cnt] = y;
    next[cnt] = head[x];
    head[x] = cnt;
}

主函数

int main() {
    scanf("%d", &n);
    for(int i = 1, x, y; i < n; ++i) {
        scanf("%d %d", &x, &y);
        adde(x, y);
        adde(y, x);
    }
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &v[i]);
    }
    dfs(1, 0, 0);
    printf("%lld %lld", mx, (ans * 2) % 10007);
    return 0;
}

关键：dfs

void dfs(int x, int fa, int grfa) {
    ans += v[x] * v[grfa];
    mx = max(mx, v[x] * v[grfa]);
/*直接循环判断太慢
*   for(int i = head[x]; i; i = next[i]) if(to[i] != fa) {
*       for(int j = next[i]; j; j = next[j]) if(to[j] != fa) {
*           ans += v[to[i]] * v[to[j]];
*           mx = max(mx, v[to[i]] * v[to[j]]);
*       }
*       dfs(to[i], x, fa);
*   }
*/
    ll bsum = 0, bmx = 0;
    for(int i = head[x]; i; i = next[i]) if(to[i] != fa) {
        ans += v[to[i]] * bsum;
        mx = max(mx, v[to[i]] * bmx);
        bsum += v[to[i]];
        bmx = max(v[to[i]], bmx);
        dfs(to[i], x, fa);
    }
}

注意到一开始使用的二重循环，复杂度高达$O(N^2)$，实在是太naive了。
观察到如果固定了j，就相当于枚举每个在j之前的i，于是就利用了前缀和的思想进行优化，复杂度降低到$O(N)$。