POJ 3107 Godfather(树的重心)

嘟嘟嘟

题说的很明白,就是求树的重心。

我们首先dfs一遍维护每一个点的子树大小,然后再dfs一遍,对于一个点u,选择子树中size[v]最小的那个和n - size[u]比较,取最大作为删除u后的答案Max[u]。

然后再O(n)遍历一遍取min(Max[i]).

写代码的时候两次dfs可以合并。

然后这题竟然卡vector,不得不用链前存图……简直有毒。

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 5e4 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n;
struct Node
{
int nxt, to;
}e[maxn << ];
int head[maxn], ecnt = ;
void add(int x, int y)
{
e[++ecnt].to = y;
e[ecnt].nxt = head[x];
head[x] = ecnt;
} bool vis[maxn];
int siz[maxn], Max[maxn];
void dfs(int now, int fa)
{
siz[now] = ; Max[now] = -;
for(int i = head[now]; i; i = e[i].nxt)
{
if(e[i].to == fa) continue;
dfs(e[i].to, now);
siz[now] += siz[e[i].to];
Max[now] = max(Max[now], siz[e[i].to]);
}
Max[now] = max(Max[now], n - siz[now]);
} int main()
{
n = read();
Mem(vis, ); Mem(head, ); ecnt = ;
for(int i = ; i < n; ++i)
{
int x = read(), y = read();
add(x, y); add(y, x);
}
dfs(, );
int Min = INF;
for(int i = ; i <= n; ++i) Min = min(Min, Max[i]);
for(int i = ; i <= n; ++i) if(Max[i] == Min) write(i), space;
enter;
return ;
}
上一篇:JAVA验证身份证格式及合法性


下一篇:node.js基础 1之 URL网址解析的好帮手