Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #221 - FSELECT - pirate
Ngày: 15-11-2011
Cập nhật: 16-11-2011
Người gửi: khanhptnk
Ngôn ngữ: C++
Xem: 558

Điểm: 4.2/5 (9 Phiếu)


#include <iostream>
#include <cstdio>
#include <vector>
#define MAXN 200001
using namespace std;
 
vector <int> e[MAXN], app[MAXN];
 
int maxCon[MAXN], size[MAXN], h[MAXN], pre[MAXN], par[MAXN], lev[MAXN];
 
int n, k, root;
 
void read() {
   scanf("%d%d", &n, &k);
   for (int i = 1; i <= n; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      app[x].push_back(i);
      if (y != 0) {
         e[i].push_back(y);
         e[y].push_back(i);
      }
      else root = i;
   }
}
 
void dfs1(int u) {
   maxCon[u] = -1;
   size[u] = 1;
   int lim = e[u].size();
   for (int i = 0; i < lim; i++) {
      int v = e[u][i];
      if (v != pre[u]) {
         pre[v] = u;
         h[v] = h[u] + 1;
         dfs1(v);
         if (maxCon[u] == -1 || size[v] > size[maxCon[u]]) 
            maxCon[u] = v;
         size[u] += size[v];
      }
   }
}
 
void dfs2(int u) {
   if (maxCon[u] != -1) {
      par[maxCon[u]] = par[u];
      lev[maxCon[u]] = lev[u];
      dfs2(maxCon[u]);
   }
   int lim = e[u].size();
   for (int i = 0; i < lim; i++) {
      int v = e[u][i];
      if (v == maxCon[u]) continue;
      if (v != pre[u]) {
         par[v] = v;
         lev[v] = lev[u] + 1;
         dfs2(v);
      }
   }
}
 
int LCA(int x, int y) {
   if (lev[x] < lev[y]) swap(x, y);
   while (lev[x] > lev[y]) x = pre[par[x]];
   while (par[x] != par[y]) {
      x = pre[par[x]];
      y = pre[par[y]];
   }
   return h[x] < h[y] ? x : y;
}
 
int dist(int x, int y) {
   return h[x] + h[y] - h[LCA(x, y)] * 2;
}
 
void process() {
   dfs1(root);
   par[root] = root;
   dfs2(root);
 
   for (int i = 1; i <= k; i++) {
      int lim = app[i].size();
      int best = -1;
      for (int j = 0; j < lim; j++)
         if (best == -1 || h[app[i][j]] > h[best]) best = app[i][j];
      int ans = -1;
      for (int j = 0; j < lim; j++) {
         ans = max(ans, dist(best, app[i][j]));
      }
      printf("%d\n", ans);
   }
}
 
int main() {
   //freopen("fselect.inp", "r", stdin);
   //freopen("fselect.out", "w", stdout);
 
   read();
   process();
 
}