Advertisement
Manioc

QTREE5

Oct 7th, 2018
224
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAX 100007
  3. #define INF 1e18+7
  4. #define LOG 50
  5.  
  6. using namespace std;
  7.  
  8. vector<int> graph[MAX];
  9. struct Centroid {
  10.     int vis[MAX], siz[MAX], root;
  11.     int parent[MAX], layer[MAX];
  12.     int state[MAX];
  13.  
  14.     vector<int> tree[MAX];
  15.  
  16.     void init(){
  17.         for(int i = 0; i < MAX; i++){
  18.             vis[i] = siz[i] = layer[i] = parent[i] = state[i] = 0;
  19.             tree[i].clear();
  20.         }
  21.     }
  22.  
  23.     int getCent(int u, int n, int p = 0){
  24.         for(int i = 0; i < graph[u].size(); i++){
  25.             int v = graph[u][i];
  26.             if(!vis[v] && v != p && siz[v] > n/2) return getCent(v, n, u);
  27.         }
  28.  
  29.         return u;
  30.     }
  31.     int find(int u, int p = 0){
  32.         siz[u] = 1;
  33.         for(int i = 0; i < graph[u].size(); i++){
  34.             int v = graph[u][i];
  35.             if(v != p && !vis[v]){
  36.                 find(v, u);
  37.                 siz[u] += siz[v];
  38.             }
  39.         }
  40.  
  41.         return p? 0: getCent(u, siz[u]);
  42.     }
  43.  
  44.     void build(int u = 0){
  45.         if(u == 0){
  46.             u = root = find(1);
  47.             vis[u] = 1;
  48.             layer[u] = 1;
  49.         }
  50.  
  51.         for(int i = 0; i < graph[u].size(); i++){
  52.             int v = graph[u][i];
  53.             if(!vis[v]){
  54.                 int x = find(v);
  55.                 vis[x] = 1;
  56.                 layer[x] = layer[u] + 1;
  57.                 parent[x] = u;
  58.  
  59.                 tree[u].push_back(x);
  60.                 tree[x].push_back(u);
  61.                 build(x);
  62.             }
  63.         }
  64.     }
  65.  
  66.     vector<int> operator[](int i)const{
  67.         return tree[i];
  68.     }
  69. } c;
  70.  
  71. int vis[MAX], parent[LOG][MAX];
  72. long long h[MAX];
  73. void dfs(int no){
  74.     vis[no] = true;
  75.  
  76.     for(int i = 0; i < graph[no].size(); i++){
  77.         int v = graph[no][i];
  78.         if(!vis[v]){
  79.            h[v] = h[no] + 1;
  80.            parent[0][v] = no;
  81.            dfs(v);
  82.         }
  83.     }
  84. }
  85.  
  86. void build(int no){
  87.     parent[0][no] = no;
  88.  
  89.     for(int i = 1; (1 << i) <= MAX; i++){
  90.         for(int j = 1; j <= MAX; j++){
  91.             parent[i][j] = parent[i-1][parent[i-1][j]];
  92.         }
  93.     }
  94. }
  95.  
  96. int lca(int u, int v){
  97.     if(h[u] < h[v]) swap(u, v);
  98.  
  99.     int lg;
  100.     for(lg = 1; (1 << lg) <= h[u]; lg++);
  101.     lg--;
  102.  
  103.     for(int i = lg; i >= 0; i--){
  104.         if(h[parent[i][u]] >= h[v]) u = parent[i][u];
  105.     }
  106.  
  107.     if(u == v) return u;
  108.  
  109.     for(int i = lg; i >= 0; i--){
  110.         if(parent[i][u] != parent[i][v]){
  111.             u = parent[i][u];
  112.             v = parent[i][v];
  113.         }
  114.     }
  115.  
  116.     return parent[0][u];
  117. }
  118.  
  119. multiset<long long> dists[MAX];
  120. void update(int no){
  121.     //cout << "Adicionando...\n";
  122.     int neigh = c.parent[no];
  123.     dists[no].insert(0);
  124.     while(neigh != 0){
  125.         //cout << "parent -> " << neigh;
  126.         int ancestor = lca(no, neigh);
  127.         long long dist = h[no]+h[neigh]-2*h[ancestor];
  128.         //cout << " a distancia " << dist << endl;
  129.         //cout << "o parente de " << no << " e " << neigh << " is " << ancestor << endl;
  130.         dists[neigh].insert(dist);
  131.         neigh = c.parent[neigh];
  132.     }
  133. }
  134.  
  135. void rmv(int no){
  136.     //cout << "removendo...\n";
  137.     int neigh = c.parent[no];
  138.     dists[no].erase(0);
  139.     while(neigh != 0){
  140.         //cout << "parent -> " << neigh;
  141.         int ancestor = lca(no, neigh);
  142.         long long dist = h[no]+h[neigh]-2*h[ancestor];
  143.         //cout << " a distancia " << dist << endl;
  144.         //cout << "o parente de " << no << " e " << neigh << " is " << ancestor << endl;
  145.         dists[neigh].erase(dist);
  146.         neigh = c.parent[neigh];
  147.     }
  148. }
  149.  
  150. long long solve(int no){
  151.     int neigh = c.parent[no];
  152.    
  153.     multiset<long long>::iterator it = dists[no].begin();
  154.     long long ans = *it;
  155.     while(neigh != 0){
  156.         it = dists[neigh].begin();
  157.         int ancestor = lca(no, neigh);
  158.         long long dist = *it + (h[no]+h[neigh]-2*h[ancestor]);
  159.         ans = min(ans, dist);
  160.         neigh = c.parent[neigh];
  161.     }
  162.  
  163.     return ans;
  164. }
  165. int main(){
  166.     c.init();
  167.     int n; scanf("%d", &n);
  168.     for(int i = 0; i < n-1; i++){
  169.         int a, b; scanf("%d %d", &a, &b);
  170.         graph[a].push_back(b);
  171.         graph[b].push_back(a);
  172.     }
  173.     c.build();
  174.     dfs(1);
  175.     build(1);
  176.     for(int i = 1; i <= n; i++) dists[i].insert(INF);
  177.     int q; scanf("%d", &q);
  178.     while(q--){
  179.         int type, no; scanf("%d %d", &type, &no);
  180.         if(type == 0){
  181.             c.state[no] ^= 1;
  182.             if(c.state[no]) update(no);
  183.             else rmv(no);
  184.  
  185.         }else {
  186.             long long resp = solve(no);
  187.             printf("%lld\n", resp == INF? -1: resp);
  188.         }
  189.     }
  190.     return 0;
  191. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement