本文共 2235 字，大约阅读时间需要 7 分钟。
这种图论题已经变得简单了。。。
1 /* D */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int maxn = 123460; 43 vi vc[maxn], vc2[maxn]; 44 bool visit[maxn]; 45 bool mark[maxn]; 46 int markp[maxn], pre[maxn]; 47 int mx[maxn], mx_[maxn]; 48 int n, m, length = 0; 49 int mn = INT_MAX, ans = INT_MAX; 50 51 void bfs(int s) { 52 queue Q; 53 int u, v, sz; 54 55 Q.push(s); 56 visit[s] = true; 57 pre[s] = 0; 58 59 while (!Q.empty()) { 60 u = Q.front(); 61 Q.pop(); 62 sz = SZ(vc[u]); 63 rep(i, 0, sz) { 64 v = vc[u][i]; 65 if (!visit[v]) { 66 visit[v] = true; 67 pre[v] = u; 68 Q.push(v); 69 } 70 } 71 } 72 } 73 74 void dfs3(int v) { 75 if (visit[v]) 76 return; 77 78 visit[v] = true; 79 int u = pre[v]; 80 81 length += 2; 82 vc2[u].pb(v); 83 vc2[v].pb(u); 84 if (u) 85 dfs3(u); 86 } 87 88 void dfs(int u, int fa) { 89 int v, sz = SZ(vc2[u]); 90 91 mx[u] = mx_[u] = 0; 92 rep(i, 0, sz) { 93 v = vc2[u][i]; 94 if (v == fa) 95 continue; 96 97 dfs(v, u); 98 if (mx[v]+1 > mx[u]) { 99 mx_[u] = mx[u];100 mx[u] = mx[v] + 1;101 } else if (mx[v]+1 > mx_[u]) {102 mx_[u] = mx[v]+1;103 }104 }105 106 #ifndef ONLINE_JUDGE107 printf("u = %d, mx[u] = %d, mx_[u] = %d\n", u, mx[u], mx_[u]);108 #endif109 }110 111 void dfs2(int u, int fa, int pmx) {112 int v, sz = SZ(vc2[u]);113 int cmx = max(mx[u], pmx), tmp;114 115 if (length-cmx < mn) {116 mn = length - cmx;117 ans = u;118 } else if (length-cmx==mn && u
转载于:https://www.cnblogs.com/bombe1013/p/4926704.html