面试题一则 | Eurce's Blog

有节点数为n的一棵树，每个节点i有一个权值w[i]，节点i到节点j的距离d[i][j]定义为在树上节点i和节点j之间有多少条边。定义f(i) = sum{w[j] * d[i][j] | -1 < j < n}，求min{f(i) | -1 < i < n}。题源来自qoshi。

基本思路还是树型DP，希望能根据相邻节点的f值计算出当前节点的f值。具体的思路是，如果指定了深搜的起点为0，那么每个节点都会将树上的其他节点分为两个部分，一部分是离0点近的（设为A类节点），一部分是离0点远的（设为B类节点）。

具体的状态转移，包括4个矩阵：lw[i]，记录的是某个节点划分出的属于A类节点的权值和；rw[i]记录属于B类节点的权值和；lws[i]记录的是sum{ w[j] * d[i][j] | j属于i划分出的A类节点}；rws[i]记录的是sum{ w[j] * d[i][j] | j属于i划分出的B类节点}。由此f(i) = lws[i] + rws[i]。使用这4个矩阵是因为，沿着某条边走一步后，某个节点的这4个值可以根据相邻节点的信息O(1)地得到。

其中rws[i]，需要从自底向上的构造，也就是用了深搜遍历完所有孩子节点后，再计算父节点的值；而lws[i]，则是自顶向下的计算。

具体的程序如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define M 100000

int n, w[M], lw[M], lws[M], rw[M], rws[M], hd[M], el;
int ansi, ans;

struct E {
    int v, p;
}e[M*2];

void adde(int u, int v) {
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
    e[el].v=u; e[el].p=hd[v]; hd[v]=el++;
}

void init() {
    int i, j, k, l;
    el=0;
    memset(hd, -1, sizeof hd);
    for(i=0; i<n; i++) scanf("%d", w+i);
    for(i=1; i<n ;i++) {
        scanf("%d%d", &j, &k);
        adde(j, k);
    }
    ans=0x7fffffff;
}

void dfsr(int i, int f) {
    int j, k, l;
    rw[i]=rws[i]=0;
    for(l=hd[i]; l!=-1; l=e[l].p) {
        j=e[l].v;
        if(j==f) continue;
        dfsr(j, i);
        rw[i]+=rw[j]+w[j];
        rws[i]+=rws[j]+rw[j]+w[j];
    }
}

void dfsl(int i, int f) {
    int j, k, l;
    if(f==-1) {
        lw[i]=lws[i]=0;
    } else {
        lw[i]=rw[f]+lw[f]-rw[i]-w[i]+w[f];
        lws[i]=rws[f]+lws[f]-rws[i]-rw[i]-w[i]+lw[i];
    }
    for(l=hd[i]; l!=-1; l=e[l].p) {
        j=e[l].v;
        if(j==f) continue;
        dfsl(j, i);
    }
}

void solve() {
    int i;
    dfsr(0, -1);
    dfsl(0, -1);
    for(i=0; i<n; i++) {
        printf("%d: %d + %d = %d\n", i, lws[i], rws[i], lws[i]+rws[i]);
        if(lws[i]+rws[i]<ans) {
            ans=lws[i]+rws[i];
            ansi=i;
        }
    }
    printf("%d %d\n", ansi, ans);
}

int main () {
    while(~scanf("%d", &n)) {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 100000

int n, w[M], lw[M], lws[M], rw[M], rws[M], hd[M], el;

int ansi, ans;

struct E {

int v, p;

}e[M*2];

void adde(int u, int v) {

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

e[el].v=u; e[el].p=hd[v]; hd[v]=el++;

}

void init() {

int i, j, k, l;

el=0;

memset(hd, -1, sizeof hd);

for(i=0; i<n; i++) scanf("%d", w+i);

for(i=1; i<n ;i++) {

scanf("%d%d", &j, &k);

adde(j, k);

}

ans=0x7fffffff;

}

void dfsr(int i, int f) {

int j, k, l;

rw[i]=rws[i]=0;

for(l=hd[i]; l!=-1; l=e[l].p) {

j=e[l].v;

if(j==f) continue;

dfsr(j, i);

rw[i]+=rw[j]+w[j];

rws[i]+=rws[j]+rw[j]+w[j];

}

void dfsl(int i, int f) {

int j, k, l;

if(f==-1) {

lw[i]=lws[i]=0;

} else {

lw[i]=rw[f]+lw[f]-rw[i]-w[i]+w[f];

lws[i]=rws[f]+lws[f]-rws[i]-rw[i]-w[i]+lw[i];

}

for(l=hd[i]; l!=-1; l=e[l].p) {

j=e[l].v;

if(j==f) continue;

dfsl(j, i);

}

void solve() {

int i;

dfsr(0, -1);

dfsl(0, -1);

for(i=0; i<n; i++) {

printf("%d: %d + %d = %d\n", i, lws[i], rws[i], lws[i]+rws[i]);

if(lws[i]+rws[i]<ans) {

ans=lws[i]+rws[i];

ansi=i;

}

printf("%d %d\n", ansi, ans);

}

int main () {

while(~scanf("%d", &n)) {

init();

solve();

}

return 0;

}

只有自己做的一些测试数据，没有找到OJ版本的题目：

输入1：

2 3 1 2 4

0 1

1 2

2 3

2 4

输出1：

0: 0 + 23 = 23
1: 2 + 13 = 15
2: 7 + 6 = 13
3: 21 + 0 = 21
4: 17 + 0 = 17
2 13

0: 0 + 23 = 23

1: 2 + 13 = 15

2: 7 + 6 = 13

3: 21 + 0 = 21

4: 17 + 0 = 17

2 13

输入2：

9
5 2 7 6 8 1 4 2 3
0 1
1 2
1 3
3 5
3 6
3 4
4 7
0 8

5 2 7 6 8 1 4 2 3

0 1

1 2

1 3

3 5

3 6

3 4

4 7

0 8

输出2：

0: 0 + 78 = 78
1: 11 + 45 = 56
2: 80 + 0 = 80
3: 35 + 17 = 52
4: 68 + 2 = 70
5: 88 + 0 = 88
6: 82 + 0 = 82
7: 104 + 0 = 104
8: 110 + 0 = 110
3 52

0: 0 + 78 = 78

1: 11 + 45 = 56

2: 80 + 0 = 80

3: 35 + 17 = 52

4: 68 + 2 = 70

5: 88 + 0 = 88

6: 82 + 0 = 82

7: 104 + 0 = 104

8: 110 + 0 = 110

3 52