题意
变相考察求树的重心。
思路
代码
|
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 80 81 82 83 84 85 86 87 88 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXV = 20005; const int MAXE = 40005; struct Graph { int siz[MAXV]; int dp[MAXV]; int par[MAXV]; int head[MAXV]; int nxt[MAXE]; int end[MAXE]; int tot; void init() { memset(head,0,sizeof(head)); tot = 2; } void addEdge(int from,int to) { end[tot] = to; nxt[tot] = head[from]; head[from] = tot++; } } gph; int n; void dfs(int cur,int par) { gph.par[cur] = par; gph.siz[cur] = 1; gph.dp[cur] = 1; for(int j = gph.head[cur]; j; j = gph.nxt[j]) { int now = gph.end[j]; if(now != par) { dfs(now,cur); gph.siz[cur] += gph.siz[now]; gph.dp[cur] = max(gph.siz[now],gph.dp[cur]); } } } int balance() { dfs(1,0); int ret = -1; for(int i = 1; i <= n; i++) { int dpn = max(gph.dp[i],n-gph.siz[i]); if(dpn <= n/2) { printf("%d\n",i); ret = 0; } } return ret; } int main() { scanf(" %d",&n); gph.init(); for(int i = 1; i < n ; i++) { int a,b; scanf(" %d %d",&a,&b); gph.addEdge(a,b); gph.addEdge(b,a); } int res = balance(); if(res == -1) { puts("NONE"); } return 0; } |
