2012-12-02 16:55:03Morris
[ZJ][一年後修正版][樹型DP] b174. 旅游规划
內容 ：
W市的交通规划出现了重大问题，市政府下决心在全市的各大交通路口安排交通疏导员来疏导密集的车流。但由于人员不足，W市市长决定只在最需要安排人员的路口安放人员。具体说来，W市的交通网络十分简单，它包括n个交叉路口和n-1条街道，任意一条街道连接两个交叉路口，并且任意两个交叉路口之间都存在一条路径互相连接。经过长期调查结果显示如果一个交叉路口位于W市交通网的最长路径上，那么这个路口必然拥挤不堪，所谓最长路径定义为某条路径p=(v1,v2,v3…vk)，路径经过的路口各不相同且城市中不存在长度>k的路径（因此可能存在着不唯一的最长路径）。因此W市市长希望知道有哪些路口位于城市交通网的最长路径之上。
輸入說明
：
第一行包括一个整数n。
之后的n-1行每行包括两个整数u, v表示编号为u和v的路口之间存在着一条街道（注意：路口被依次编号为0到n-1）
輸出說明
：
输出包括若干行，每行包括一个整数——某个位于最长路上路口的编号。
为了确保解唯一，我们规定位于所有最长路上的路口按编号顺序从小到大输出。
範例輸入 ：
10 0 1 0 2 0 4 0 6 0 7 1 3 2 5 4 8 6 9
範例輸出 ：
0 1 2 3 4 5 6 8 9
提示
：
说明：
这里存在着若干条最长路径，其中的两条是3-1-0-2-5与8-4-0-6-9，他们的长度都是5，但是不存在长度>5的路径且所有最长路径都不包括路口7，所以答案中没有7。
数据范围：
对于50%的数据保证n<=1000
对于100%的数据保证n<=200000
这里存在着若干条最长路径，其中的两条是3-1-0-2-5与8-4-0-6-9，他们的长度都是5，但是不存在长度>5的路径且所有最长路径都不包括路口7，所以答案中没有7。
数据范围：
对于50%的数据保证n<=1000
对于100%的数据保证n<=200000
出處
：
2008 海峽兩岸青少年程式設計競賽
做法 : 兩次 dfs,
1st dfs :
得到由下而上的最大高度 (要記錄第一高 第二高),
意即 得到每個節點的 subtree 的高度
2nd dfs :
將父節點高度轉過來, 這時要注意, 如果第一高是從這個節點接上去的, 那麼就抓第二高+1,
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
unsigned short dp1[200000][2], dp2[200000];
vector<int> g[200000];
void dfs1(int nd, int p) {
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(*it != p) {
dfs1(*it, nd);
if(dp1[*it][0]+1 > dp1[nd][1])
dp1[nd][1] = dp1[*it][0]+1;
if(dp1[nd][0] < dp1[nd][1])
swap(dp1[nd][0], dp1[nd][1]);
}
}
}
void dfs2(int nd, int p) {
if(nd) {
if(dp1[nd][0]+1 == dp1[p][0])
dp2[nd] = max(dp1[p][1], dp2[p])+1;
else
dp2[nd] = max(dp1[p][0], dp2[p])+1;
}
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(*it != p)
dfs2(*it, nd);
}
}
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, i, x, y;
scanf("%d", &n);
for(i = 1; i < n; i++) {
ReadInt(&x);
ReadInt(&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(0, -1);
dfs2(0, -1);
int longest = 0;
for(i = 0; i < n; i++) {
longest = max(longest, dp1[i][0]+dp1[i][1]);
longest = max(longest, dp1[i][0]+dp2[i]);
}
for(i = 0; i < n; i++) {
if(longest == dp1[i][0]+dp1[i][1] ||
longest == dp1[i][0]+dp2[i]) {
printf("%d\n", i);
}
}
return 0;
}
做法 : 兩次 dfs,
1st dfs :
得到由下而上的最大高度 (要記錄第一高 第二高),
意即 得到每個節點的 subtree 的高度
2nd dfs :
將父節點高度轉過來, 這時要注意, 如果第一高是從這個節點接上去的, 那麼就抓第二高+1,
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
unsigned short dp1[200000][2], dp2[200000];
vector<int> g[200000];
void dfs1(int nd, int p) {
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(*it != p) {
dfs1(*it, nd);
if(dp1[*it][0]+1 > dp1[nd][1])
dp1[nd][1] = dp1[*it][0]+1;
if(dp1[nd][0] < dp1[nd][1])
swap(dp1[nd][0], dp1[nd][1]);
}
}
}
void dfs2(int nd, int p) {
if(nd) {
if(dp1[nd][0]+1 == dp1[p][0])
dp2[nd] = max(dp1[p][1], dp2[p])+1;
else
dp2[nd] = max(dp1[p][0], dp2[p])+1;
}
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(*it != p)
dfs2(*it, nd);
}
}
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, i, x, y;
scanf("%d", &n);
for(i = 1; i < n; i++) {
ReadInt(&x);
ReadInt(&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(0, -1);
dfs2(0, -1);
int longest = 0;
for(i = 0; i < n; i++) {
longest = max(longest, dp1[i][0]+dp1[i][1]);
longest = max(longest, dp1[i][0]+dp2[i]);
}
for(i = 0; i < n; i++) {
if(longest == dp1[i][0]+dp1[i][1] ||
longest == dp1[i][0]+dp2[i]) {
printf("%d\n", i);
}
}
return 0;
}