| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
太奇葩了,思路是很清楚的,但是感觉结构比较奇葩,思想上应该是dp树#include <iostream>
#include <vector>
using namespace std;
#define MAX 20001
#define max(a, b) (a) > (b) ? (a) : (b)
void POJ1655();
typedef pair<int, int> Pair;
int N;
//using adjacent table to store the graph
//就是他!!!很奇葩的呢
vector<Pair> node[MAX];
/********把你围起来*******/
int minVal[MAX];
int main(int argc, const char * argv[]){
POJ1655();
return 0;
}
void input() {
int a, b;
for (int i = 1; i < N; i ++) {
node[i].clear();
}
for (int i = 1; i < N; i ++) {
cin >> a >> b;
//construct the graph
node[a].push_back(Pair(b,-1));
node[b].push_back(Pair(a,-1));
}
}
int dfs(int pre, int next) {
int l = 0;
for (int i = 0; i < node[next].size(); i ++) {
if (node[next][i].first != pre) {
if (node[next][i].second == -1) {
node[next][i].second = dfs(next, node[next][i].first);
}
l += 1 + node[next][i].second;
}
}
return l;
}
void dfs() {
//core code
int m;
for (int i = 1; i <= N; i ++) {
m = 0;
for (int j = 0; j < node[i].size(); j ++) {
node[i][j].second = dfs(i, node[i][j].first);
m = max(m, node[i][j].second+1);
}
minVal[i] = m;
}
return ;
}
Pair maxVal() {
int m = minVal[1], id = 1;
for (int i = 2 ; i <= N; i ++) {
if (m > minVal[i]) { m = minVal[i]; id = i; }
}
return Pair(id, m);
}
void POJ1655() {
int num;
cin >> num;
while (num --) {
cin >> N;
input();
dfs();
Pair rsl = maxVal();
cout<<rsl.first<<" "<<rsl.second<<endl;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator