[NOIP 2014 提高组] 联合权值

形式化题目

给定一棵 $n$ 个点的树，点 $i$ 有权值 $w_i$ 。若两个不同点 $u, v$ 之间的距离为 2，则有序点对 $(u, v)$ 产生联合权值 $w_u \cdot w_v$ 。

要求：

所有距离为 2 的有序点对中，联合权值的最大值；
所有距离为 2 的有序点对的联合权值之和，对 $10007$ 取模。

注意点对是有序的： $(u, v)$ 与 $(v, u)$ 是两个不同的点对，都要计入总和。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * 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-08-12 23:00
 * update_at: 2026-08-12 23:00
 */
// brute.cpp：小数据暴力解，枚举所有距离为 2 的有序点对（BFS 爬两层邻居实现），
// 用来理解题意并辅助对拍，只适合 n <= 30 的小数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n;
int w[MAXN];         // w[i] 表示点 i 的权值
vector<int> g[MAXN]; // 邻接表存树
int dis[MAXN];       // BFS 中每个点到起点 u 的距离，-1 表示未访问

long long total_sum; // 所有有序点对联合权值之和，最后对 10007 取模
int max_value;       // 联合权值最大值

// 从 u 出发 BFS 爬两层邻居，找出所有距离恰好为 2 的点 v：
// 每个 (u, v) 是一个距离为 2 的有序点对，贡献 w[u] * w[v]。
void bfs_collect(int u) {
    memset(dis, -1, sizeof(dis));
    queue<int> q;
    dis[u] = 0;
    q.push(u);

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < (int)g[x].size(); i++) {
            int v = g[x][i];
            if (dis[v] != -1) continue; // 已经访问过
            dis[v] = dis[x] + 1;
            if (dis[v] < 2) q.push(v); // 距离 2 的点不需要再向外扩展
        }
    }

    for (int v = 1; v <= n; v++) {
        if (dis[v] == 2) {
            int value = w[u] * w[v];
            total_sum += value;
            if (value > max_value) max_value = value;
        }
    }
}

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

    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> w[i];

    // 枚举每个起点，BFS 找它所有距离为 2 的点，逐对统计。
    for (int u = 1; u <= n; u++) {
        bfs_collect(u);
    }

    cout << max_value << ' ' << total_sum % 10007 << '\n';
    return 0;
}

brute.cpp 从每个点 $u$ 出发 BFS 爬两层邻居，把距离恰好为 2 的点 $v$ 全部找出，直接累加 $w_u \cdot w_v$ 并更新最大值。它逐对枚举，每个起点都要扫一遍整棵树，复杂度 $O(n^2)$ ，只能处理 $n \leqslant 30$ 的小数据。

关键观察：距离为 2 的点对必然共用一个中间点。点 $u, v$ 距离为 2 当且仅当存在点 $x$ 同时与 $u, v$ 相邻（树中这个 $x$ 唯一）。所以 $x$ 的任意两个不同邻居 $a, b$ 恰好确定两个有序点对 $(a, b)$ 和 $(b, a)$ ，联合权值都是 $w_a w_b$ 。

设 $x$ 的邻居权值之和为 $S = \sum w_i$ 、平方和为 $Q = \sum w_i^2$ ，则经过 $x$ 的全部有序点对贡献为：

S^2 - Q = \left(\sum w_i\right)^2 - \sum w_i^2 = 2\sum_{a < b} w_a w_b

这个式子来自完全平方展开：把 $\left(\sum w_i\right)^2$ 拆开，每一项是两两相乘 $w_a w_b$ ，其中既包含 $a = b$ 的自乘项 $\sum w_i^2$ ，也包含所有 $a \neq b$ 的交叉项；而每对不同的 $a, b$ 会以 $(a, b)$ 与 $(b, a)$ 两种顺序各出现一次，所以交叉项恰为 $2\sum_{a < b} w_a w_b$ 。因此：

\left(\sum w_i\right)^2 = \sum w_i^2 + 2\sum_{a < b} w_a w_b \implies S^2 - Q = 2\sum_{a < b} w_a w_b

右边正好是“任意两个不同邻居、两个方向、每对一次”的总和：平方和项 $Q$ 的作用是把 $a = b$ 的虚假对减掉。最大值更简单：有序对两个方向的乘积相同，所以经过 $x$ 的最大联合权值就是邻居权值中最大两个 $m_1 \geqslant m_2$ 的乘积 $m_1 m_2$ 。

于是对每个点只做一次邻居扫描，同时维护 $S$ 、 $Q$ 、 $m_1$ 、 $m_2$ 四个量即可。以样例（路径 $1-2-3-4-5$ ，权值 $1, 5, 2, 3, 10$ ）为例，下表展示每个中间点的聚合结果：

中间点 x	邻居及权值	S	Q	S²−Q（有序对总和）	前两大乘积
2	1(1)、3(2)	3	5	4	2
3	2(5)、4(3)	8	34	30	15
4	3(2)、5(10)	12	104	40	20

表格中行表示一个中间点，列依次是邻居权值、 $S$ 、 $Q$ 、 $S^2-Q$ 与最大两权值乘积。总和 $4 + 30 + 40 = 74$ ，最大值 $\max(2, 15, 20) = 20$ ，与样例输出 20 74 一致；每行的 $S^2 - Q$ 都等于该中间点两个方向有序点对贡献之和（例如中间点 3 贡献 $(2,4)$ 与 $(4,2)$ 共 $2 \times 15 = 30$ ）。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * 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-08-12 23:00
 * update_at: 2026-08-12 23:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int MOD = 10007;

int n;
int w[MAXN];         // w[i] 表示点 i 的权值
vector<int> g[MAXN]; // 邻接表存树，仿照 rbook 模板 dfs-traversal 的建图方式

long long sum_total; // 所有有序点对联合权值之和，最后统一对 10007 取模
int max_value;       // 联合权值最大值

// 对中间点 u 的邻居做一次扫描：维护权值和、权值平方和、最大与次大权值。
void update_node(int u) {
    if ((int)g[u].size() < 2) return; // 少于两个邻居不会产生距离为 2 的点对

    long long sum = 0; // 邻居权值之和 S
    long long sq = 0;  // 邻居权值平方和 Q
    int max1 = 0;      // 邻居中最大权值
    int max2 = 0;      // 邻居中次大权值

    for (int i = 0; i < (int)g[u].size(); i++) {
        int value = w[g[u][i]];
        sum += value;
        sq += (long long)value * value;
        if (value > max1) {
            max2 = max1;
            max1 = value;
        } else if (value > max2) {
            max2 = value;
        }
    }

    // 经过 u 的有序点对总和 = S^2 - Q = 2 * sum_{a<b} w[a]*w[b]
    // 每个无序对的两个方向 (a,b)、(b,a) 都恰好被算一次。
    sum_total += sum * sum - sq;
    if (max1 * max2 > max_value) max_value = max1 * max2; // 有序对两个方向乘积相同
}

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

    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> w[i];

    for (int u = 1; u <= n; u++) {
        update_node(u);
    }

    cout << max_value << ' ' << sum_total % MOD << '\n';
    return 0;
}

代码里 update_node(u) 对点 u 的邻居做一次扫描：sum、sq 对应 $S$ 、 $Q$ ，max1、max2 用两个 if 维护前两大权值；sum * sum - sq 与 value * value 都先转 long long 防止溢出，总和最后统一对 $10007$ 取模。

DFS 版本

上面的做法按点扫邻居，也可以一次 DFS 完成：把 $1$ 号点当根，距离为 2 的点对分成两类——兄弟对（共父，两个儿子之间）与祖孙对（点与它的孙子）。三个 DFS 分别处理最大值与总和：

dfs_1：对每个点维护其儿子中的最大、次大权值 max_f[u][0/1]，max_f[u][1] * max_f[u][0] 是经过它的兄弟对最大值；
dfs_2：维护孙子中的最大权值 max_chch，max_chch * w[u] 是祖孙对最大值；
dfs_sum_2：兄弟对总和用 $(\sum w_{son})^2 - \sum w_{son}^2$ （儿子权值和平方减平方和），祖孙对总和用"所有孙子权值和 × w[u] × 2"（有序对两个方向）。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180//暴力求 与点u 距离为2的点
//单独求是很简单的
//如何在一次dfs里所有的点的距离呢

//代码模板, 来自 rbook.roj.ac.cn
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//====== log 调试用
// 使用: int a,b,c; log(a,b,c)
#ifndef DEBUG
#define log(...)
#define fenc(...) ;
#else
#define fenc cout << "\n=================\n";
#define log(args...) { cout << "LINE:" << __LINE__ << " : ";string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}

template<typename T>
void err(istream_iterator<string> it, T a) {
cerr << *it << " = " << a << "\n";
}

template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << ", ";
err(++it, args...);
}
#endif

const int maxn = 1e6+5;
int n,m;
int w[maxn];
int max_ans = 0;
ll mod = 10007;
ll sum = 0;

ll ch_sum[maxn]; // sum of children
ll ch_sq_sum[maxn]; // sum of square of children 

int max_f[maxn][2]; // max_f[i][0] max_f[i][1]


// helper
void update_max_f(int i,int val) {
  if( val > max_f[i][0]) {
    max_f[i][1] = max_f[i][0];
    max_f[i][0] = val;
  }
  else if( val > max_f[i][1]) {
    max_f[i][1] = val;
  }
}

const int maxe = 1e6+5;

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }
    //返回head[u]
    int operator()(int u){ return h[u]; }
} e;


void init() {
  cin >> n;
  for(int i =1;i<n;i++){
    int u,v;
    cin >> u >> v;
    e.add2(u,v);
  }
  for(int i =1;i<=n;i++){
    cin >> w[i];
  }
}

void dfs_1(int u,int fa) {

  for(int i = e(u); ~i ;i = e[i].next)
  {
    int  v = e[i].v;
    if( v == fa) continue;
    update_max_f(u,w[v]);
    dfs_1(v,u);
  }

  // get all children info
  int t = max_f[u][1] * max_f[u][0];
  if( t > max_ans) max_ans = t;

}

void dfs_2(int u,int fa) {
  int max_chch = 0;
  for(int i = e(u); ~i ;i = e[i].next)
  {
    int  v = e[i].v;
    if( v == fa) continue;
    // cout << u << " " << v << endl; 
    if(max_chch < max_f[v][0])
      max_chch = max_f[v][0];
    dfs_2(v,u);
  }

  // get all children info
  int t = max_chch * w[u];
  // cout << u << " " << t << endl;

  // cout << max_chch;

  // cout << endl;
  // cout << endl;
  // cout << endl;

  if( t > max_ans) max_ans = t;
}


void dfs_sum_2(int u,int fa) {
  int max_chch = 0;
  ll all_chch_sum = 0;
  for(int i = e(u); ~i ;i = e[i].next)
  {
    int  v = e[i].v;
    if( v == fa) continue;
    ch_sum[u] += w[v];
    ch_sum[u] %= mod;

    ch_sq_sum[u] += w[v] * w[v];
    ch_sq_sum[u] %= mod;

    dfs_sum_2(v,u);

    all_chch_sum += ch_sum[v];
  }

  ll t = ch_sum[u] * ch_sum[u] - ch_sq_sum[u];
  sum += t;
  sum %= mod;

  sum += ( all_chch_sum * w[u]) *2;
  sum %= mod;
}

int main () {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 关闭io同步
    init();
    dfs_1(1,1);
    dfs_2(1,1);
    dfs_sum_2(1,1);
    cout << max_ans << " ";
    cout << sum << endl;

    
    return 0;
}

注意该版本把树固定成以 $1$ 为根，DFS 时用 fa 参数避免走回头路；最大值在两遍 DFS 后取 $O(1)$ 更新，总和全程对 $10007$ 取模，复杂度同为 $O(n)$ 。

复杂度

时间：每个点只扫描一次邻居，每条无向边被两个端点各看一次，总工作量 $\sum_x deg(x) = 2(n-1)$ ，即 $O(n)$ 。
空间：邻接表存树， $O(n)$ 。

总结

把“距离为 2”翻译成“共用一个中间点”，树上的二跳计数就变成了对每个点做一次邻居聚合。 $S^2 - Q$ 这个恒等式一次解决两个麻烦：有序点对要算两次方向、点对的两个点必须不同；而最大值只需在扫描中顺带维护前两大权值。本题的建图方式与 rbook 的《图的遍历》文章及其 dfs-traversal 模板（邻接表 + 无向加边）一致，本题只是不需要 DFS，直接按点扫邻居。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20朴素解（brute.cpp）
  从每个点 u 出发 BFS 爬两层邻居
  枚举所有距离为 2 的有序点对，逐个累加 w[u]*w[v]      O(n^2)
        |
        | 瓶颈：每个起点都要扫一遍整棵树，n=2e5 不可行
        v
关键观察
  距离为 2 的点对 (u,v) 共用一个中间点 x（树中唯一）
  S = 邻居权值和，Q = 邻居权值平方和
  经过 x 的有序对总和 = S^2 - Q = 2 * sum_{a<b} w[a]*w[b]
  经过 x 的最大联合权值 = 最大两个邻居权值的乘积 max1*max2
        |
        v
正式解（main.cpp）
  对每个点 x 扫描一遍邻居，同时维护 S、Q、max1、max2
  总和累加 S^2 - Q；最大值更新 max1*max2
  输出 最大值  和  总和 mod 10007
        |
        v
复杂度 O(n)（每条边被两个端点各看一次），空间 O(n)

图中三条主线分别对应“暴力在哪里慢”“观察到什么性质”“正式解如何利用这个性质”。 $S^2 - Q$ 把“枚举点对”变成“一次邻居扫描”，同时解决了有序对计数和排除相同邻居两个麻烦；最大值只需要在扫描中顺带维护前两大权值，这就是 $O(n)$ 的来源。