[NOIP 2014 提高组] 联合权值

GitHub跳转原题关系图返回列表

按中心节点聚合邻居权值，一次得到距离为 2 的有序点对总和与最大值。

OJ: luogu

题目 ID: P1351

难度:普及+/提高-

标签:树邻居聚合数学python

日期: 2026-07-17 02:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

统计距离恰好为 2 的有序点对权值乘积的最大值和总和。

思路

固定中间点 u。它的两个不同邻居形成一个距离 2 的有序点对，因此总和是 sum^2 - sumsq，最大值是邻居权值中最大两个数的乘积。

Python 知识

  • 一次扫描维护 first/second 两个最大值，不必排序邻居列表。
  • neighbor_sum * neighbor_sum - square_sum 直接排除相同邻居。
  • 正整数权值使最大值初始为 0 足够安全。

代码

python
import sys


input = sys.stdin.buffer.readline
n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
weight = [0] + list(map(int, input().split()))

maximum = total = 0
for neighbors in graph[1:]:
    if len(neighbors) < 2:
        continue
    first = second = 0
    neighbor_sum = square_sum = 0
    for neighbor in neighbors:
        value = weight[neighbor]
        neighbor_sum += value
        square_sum += value * value
        if value > first:
            first, second = value, first
        elif value > second:
            second = value
    maximum = max(maximum, first * second)
    total += neighbor_sum * neighbor_sum - square_sum
print(maximum, total % 10007)

原有 C++ 版本仍保留：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:04
 * update_at: 2026-07-17 01:04
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

复杂度

时间 O(n)，空间 O(n)。

总结

按距离 2 的中间点分类，树上的二跳计数会变成邻接表上的一次聚合。