Advertisement
cheater2k

Untitled

Jan 23rd, 2018
448
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 7e4 + 5;
  5.  
  6. int n, dep[N], par[N][18], tin[N], tout[N], TIME;
  7. vector<int> G[N];
  8. vector<int> save[3 * N];
  9. int sz;
  10. map < pair<int,int>, int > mp;
  11. map <int, int> mn[N];
  12. int dis[N];
  13.  
  14. bool check[N];
  15.  
  16. void prep(int u, int p) {
  17.     tin[u] = ++TIME;
  18.     for (int v : G[u]) if (v != p) {
  19.         par[v][0] = u;
  20.         dep[v] = dep[u] + 1;
  21.         prep(v, u);
  22.     }
  23.     tout[u] = TIME;
  24. }
  25.  
  26. int lca(int u, int v) {
  27.     if (dep[u] < dep[v]) swap(u, v);
  28.     for (int i = 17; i >= 0; --i) if (dep[par[u][i]] >= dep[v]) u = par[u][i];
  29.     for (int i = 17; i >= 0; --i) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
  30.     return u == v ? u : par[u][0];
  31. }
  32.  
  33. int dist(int u, int v) {
  34.     return dep[u] + dep[v] - 2 * dep[lca(u,v)];
  35. }
  36.  
  37. int get_par(int u, int root) {
  38.     if (u == root) return root;
  39.     if (tin[u] >= tin[root] && tin[u] <= tout[root]) {
  40.         return par[u][0];
  41.     }
  42.    
  43.     int x = lca(u, root);
  44.     if (x != u) {
  45.         return par[u][0];
  46.     }
  47.     for (int i = 17; i >= 0; --i)
  48.         if (dep[par[root][i]] > dep[u]) root = par[root][i];
  49.    
  50.     return root;
  51. }
  52.  
  53. set < pair<int,int> > seg;
  54.  
  55. bool not_in_seg(int u) {
  56.     set< pair<int,int> >::iterator it = seg.upper_bound(make_pair(tin[u], 1e9));
  57.     if (it == seg.begin()) {
  58.         return true;
  59.     }
  60.     --it;
  61.     if ((*it).second >= tout[u]) return false; else return true;
  62. }
  63.  
  64. void dfs(int u, int p) {
  65.     if (mp.find(make_pair(u, p)) != mp.end()) return;
  66.     mp[make_pair(u, p)] = ++sz;
  67.  
  68.     int id = sz;
  69.     if (G[u].size() == 1) {
  70.         save[id] = vector<int>(1, u); mn[u][p] = 0; return;
  71.     }
  72.  
  73.     int minval = 1e9;
  74.     int max_tin = -1e9, min_tout = 1e9;
  75.  
  76.     vector<int> new_save;
  77.     for (int v : G[u]) if (v != p) {
  78.         dfs(v, u);
  79.         minval = min(minval, mn[v][u] + 1);
  80.         int vv = mp[make_pair(v, u)];
  81.  
  82.         for (int w : save[vv]) {
  83.             int pw = get_par(w, u);
  84.             if (check[pw]) continue;
  85.  
  86.             if (pw != u && dist(u, pw) >= mn[pw][get_par(pw, u)]) {
  87.                 check[pw] = 1, new_save.push_back(pw);
  88.             } else check[w] = 1, new_save.push_back(w); // todo: fix
  89.         }
  90.     }
  91.  
  92.     mn[u][p] = minval;
  93.     for (int w : new_save) check[w] = 0, dis[w] = dist(u, w);
  94.     sort(new_save.begin(), new_save.end(), [&](int x, int y) {
  95.         return dis[x] < dis[y];
  96.     });
  97.  
  98.     seg.clear();
  99.     for (int w : new_save) {
  100.         // check whether {w} is valid
  101.         if (!not_in_seg(w)) continue;
  102.  
  103.         if (tin[w] < tin[u] || tin[w] > tout[u]) { // outside Subtree(u)
  104.             if (max_tin >= tin[w] || tin[w] >= min_tout) continue;
  105.  
  106.             int pw = lca(u, w);
  107.             if (w != pw) {
  108.                 seg.insert(make_pair(tin[w], tout[w])); save[id].push_back(w); continue;
  109.             }
  110.  
  111.             max_tin = max(max_tin, tin[w]);
  112.             min_tout = min(min_tout, tout[w]);
  113.  
  114.             pw = get_par(w, u);
  115.             for (int v : G[w]) {
  116.                 if (v == par[w][0]) continue;
  117.                 if (tin[v] >= tin[pw] && tin[v] <= tout[pw]) continue;
  118.  
  119.                 seg.insert(make_pair(tin[v], tout[v]));
  120.             }
  121.             seg.insert(make_pair(tin[w], tin[w]));
  122.         } else { // inside Subtree(u)
  123.             seg.insert(make_pair(tin[w], tout[w]));
  124.         }
  125.         save[id].push_back(w);
  126.     }
  127. }
  128.  
  129. int main() {
  130.     freopen("atlarge.in", "r", stdin);
  131.     freopen("atlarge.out", "w", stdout);
  132.  
  133.     scanf("%d", &n);
  134.  
  135.     for (int i = 1; i < n; ++i) {
  136.         int u, v; scanf("%d%d", &u, &v);
  137.         G[u].push_back(v); G[v].push_back(u);
  138.     }
  139.  
  140.     par[1][0] = 1;
  141.     prep(1, 1);
  142.     for (int j = 1; j <= 17; ++j) {
  143.         for (int i = 1; i <= n; ++i) par[i][j] = par[par[i][j - 1]][j - 1];
  144.     }
  145.    
  146.     for (int i = 1; i <= n; ++i) {
  147.         if (G[i].size() == 1) {
  148.             printf("1\n"); continue;
  149.         }
  150.  
  151.         dfs(i, i);
  152.         printf("%d\n", save[mp[make_pair(i, i)]].size());
  153.     }
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement