[noip2014 提高组] 联合权值

险些把@Laffey的题抢了

注意审题！！因为审题出了很多问题。

这题一眼看下去很无从下手，简单来说就是距离为2的两个点的权值之积为联合权值，让求最大联合权值和所有联合权值的总和

仔细思考一下，一棵树中存在两个距离为2的点只有两种情况，一条线和一个角：

数据有 60% 在 2000 以内，这使我萌生了暴力的想法，先拿60再说

暴搜思想(DFS)#

I. 一条线#

这种很好想，只需在dfs的基础上记录一个前驱pre，若当前父节点为x，子节点为y，那么pre与y的距离为2，w[pre] * w[j]和w[j] * w[pre]是两个联合权值。

代码

1
void dfs(int x, int pre) {
2
    v[x] = 1;
3
    for(int i = head[x]; i; i = nxt[i]) {
4
        int & y = to[i];
5
        if(!v[y]) {
6
            dfs(y, x);
7
            maxn = max(maxn, w[y] * w[pre]);
8
            sum += w[y] *w[pre] * 2;
9
            sum %= MOD;
10
        }
11
    }
12
}

这个时候，样例过了，因为样例是单链！！

II.一个角#

这种情况难度就稍微大了一些，需统计同一层所有子节点，对其进行排列组合，每种配对的情况都是两组联合权值。 (可以对比之前做过的一道深搜选数)

举个栗子：

这是一个以①为根的子树

搜到②时，无法配对，继续搜索

搜得到③时，可与②组合

搜到④时，可与②和③组合

刚好不重不漏

我们的思路是搜到每一个子节点后向回搜索同层的子节点，分别计算，为此我们要记录当前父节点下的已搜过的子节点，直接开N * N的数组会爆too large所以我们开vector<int> son[N]

做法是每搜到一个节点，先回搜同一层的子节点进行操作，然后将其编号存入son数组中为下一个节点使用，在原dfs加入

1
for(auto i : son[x]) {
2
  maxn = max(maxn, w[y] * w[i]);
3
  sum += w[y] * w[i] * 2;
4
  sum %= MOD;
5
}
6
son[x].push_back(y);

这样，一个暴力的做法就完成了。

暴力（70分）代码#

1
#include <cstdio>
2
#include <iostream>
3
#include <vector>
4

5
using namespace std;
6

7
const int N = 4000010;
8
const int MOD = 10007;
9
typedef long long ll; //记得开long long不然取模之前容易爆
10
ll maxn;
11
ll sum;
12
bool v[N];
13
int to[N], head[N], nxt[N];
14
ll w[N];
15
vector<int> son[N];
16
int tot = 0;
17

18
void add(int x, int y) {
19
    to[++tot] = y;
20
    nxt[tot] = head[x];
21
    head[x] = tot;
22
}
23

24
void dfs(int x, int pre) {
25
    v[x] = 1;
26
    for(int i = head[x]; i; i = nxt[i]) {
27
        int & y = to[i];
28
        if(!v[y]) {
29
            dfs(y, x);
30
            for(auto i : son[x]) {
31
                maxn = max(maxn, w[y] * w[i]);
32
                sum += w[y] * w[i] * 2;
33
                sum %= MOD;
34
            }
35
            son[x].push_back(y);
36
            maxn = max(maxn, w[y] * w[pre]);
37
            sum += w[y] * w[pre] * 2;
38
            sum %= MOD;
39
        }
40
    }
41
}
42

43
int main() {
44
    int n;
45
    scanf("%d", &n);
46
    for(int i = 1; i < n; ++i) {
47
        int x, y;
48
        scanf("%d%d", &x, &y);
49
        add(x, y);
50
        add(y, x);
51
    }
52
    for(int i = 1; i <= n; ++i)
53
        scanf("%d", &w[i]);
54

55
    dfs(1, 0);
56

57
    printf("%lld %lld", maxn, sum);
58
    return 0;
59
}

优化 DFS -> 树形DP#

I.一个角#

一条线的时间复杂度已经不大了，所以我们先来考虑一个角的情况

再举个相同的栗子:

回顾一下，以④为例

sum = sum + 2 \times w[2] \times w[4] + 2 \times w[3] \times w[4] = 2 \times w[4] \times (w[2] + w[3])

乘法分配律，明白吧

推广到一般的父节点x,子节点y

sum = sum + 2 \times w[y] \times s(w[\text{y前所有子节点}])

同样最值也可以这么操作

maxn = max(maxn, w[y] \times \max(w[\text{y前所有的子节点}]))

所以处理这种情况只需维护一个前缀和s[N]和一个最值m[N]就可以完成状态转移，无需遍历一遍。

1
sum += 2 * s[x] * w[y];
2
sum %= MOD;
3
maxn = max(maxn, m[x] * w[y]);
4
//注意先处理sum和maxn再转移状态，因为反之w[y]会 * w[y]自己造成问题
5
s[x] += w[y];
6
m[x] = max(m[x], w[y]);

~~把之前的循环换掉就可以a掉了~~

II.一条线#

当dfs回溯到x时

s[y] = sum(w[y\text{的所有孩子}])\\ m[y] = max(w[y\text{的所有孩子}])

你发现了什么？

其实在做上一次优化的时候一条线的情况也已经预处理好了，只需

1
sum += 2 * s[y] * w[x];
2
maxn = max(maxn, m[y] * w[x]);

就ok了

这样也不用再统计前驱了

Ac代码#

1
#include <cstdio>
2
#include <iostream>
3
#include <vector>
4

5
using namespace std;
6

7
const int N = 400010;
8
const int MOD = 10007;
9
typedef long long ll;
10
bool v[N];
11
int to[N], head[N], nxt[N]; //前向星
12
ll s[N], m[N], w[N];
13
/**
14
* s[i]表示以i为顶的一层子树节点权值和
15
* m[i]表示以i为顶的一层子树节点权值最值
16
*/
17
ll maxn = 0, sum = 0;
18
int tot = 0;
19

20
void add(int x, int y) {
21
    to[++tot] = y;
22
    nxt[tot] = head[x];
23
    head[x] = tot;
24
}
25

26
void dp(int x) {
27
    v[x] = 1;
28
    for(int i = head[x]; i; i = nxt[i]) {
29
        int & y = to[i];
30
        if(!v[y]) {
31
            dp(y);
32
            // case corner
33
            sum += 2 * s[x] * w[y];
34
            sum %= MOD;
35
            maxn = max(maxn, m[x] * w[y]);
36

37
            //case line 这个放到哪里都行，与当前层的y权值无关
38
            sum += 2 * s[y] * w[x];
39
            sum %= MOD;
40
            maxn = max(maxn, m[y] * w[x]);
41

42
            //dp
43
            s[x] += w[y];
44
            m[x] = max(m[x], w[y]);
45
        }
46
    }
47
}
48

49
int main() {
50
    int n;
51

52
    //read
53
    scanf("%d", &n);
54
    for(int i = 1; i < n; ++i) {
55
        int x, y;
56
        scanf("%d%d", &x, &y);
57
        add(x, y);
58
        add(y, x);
59
    }
60
    for(int i = 1; i <= n; ++i)
61
        scanf("%d", &w[i]);
62

63
    //dp
64
    dp(1);
65

66
    printf("%lld %lld", maxn, sum);
67
    return 0;
68
}

Star's Blog