有节点数为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]，则是自顶向下的计算。
具体的程序如下：
|
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 |
#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：
|
1 2 3 4 5 6 |
5 2 3 1 2 4 0 1 1 2 2 3 2 4 |
输出1：
|
1 2 3 4 5 6 |
0: 0 + 23 = 23 1: 2 + 13 = 15 2: 7 + 6 = 13 3: 21 + 0 = 21 4: 17 + 0 = 17 2 13 |
输入2：
|
1 2 3 4 5 6 7 8 9 10 |
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 |
输出2：
|
1 2 3 4 5 6 7 8 9 10 |
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 |