fork download 
  1. #include <bits/stdc++.h>
  2. #define FNAME ""
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXN = (int)1e5 + 5;
  6. const int LIM = (int)1e6 + 1;
  7. const long long MOD = (long long)1e13 + 15092007;
  8. #define xd '\n'
  9. #define pii pair<int, int>
  10. #define pll pair<long long, long long>
  11. #define pli pair<long long, int>
  12. #define fi first
  13. #define se second
  14. const long long base = (long long)256;
  15. const long long INF = (long long)1e14;
  16. template<class X, class Y> bool minimize(X &a, Y b) {if(a>b){a=b;return true;}return false;};
  17. template<class X, class Y> bool maximize(X &a, Y b) {if(a<b){a=b;return true;}return false;};
  18.  
  19. void HuuThien() {
  20.     ios_base::sync_with_stdio(0);
  21.     cin.tie(0); cout.tie(0);
  22.     if (fopen(FNAME".inp", "r")) {
  23.         freopen(FNAME".inp", "r", stdin);
  24.         freopen(FNAME".out", "w", stdout);
  25.     } 
  26. }
  27.  
  28. int n, q;
  29. vector<int> adj[MAXN];
  30. int Size[MAXN], parent[MAXN], heavy[MAXN];
  31. int pos[MAXN], head[MAXN], depth[MAXN], timeDFS = 0;
  32. vector<int> segTree(4 * MAXN, 0);
  33. vector<int> lazy(4 * MAXN);
  34. vector<pair<int, int>> edges;
  35.  
  36. void Push(int node, int l, int r) {
  37.     if(lazy[node]) {
  38.         segTree[node] += (r - l + 1) * lazy[node];
  39.         if(l ^ r) {
  40.             lazy[2 * node] += lazy[node];
  41.             lazy[2 * node + 1] += lazy[node];
  42.         }
  43.         lazy[node] = 0;
  44.     }
  45. }
  46.  
  47. void update(int node, int l, int r, int wl, int wr, int value) {
  48.     if(l > wr || r < wl) return;
  49.     if(l == r) {
  50.         lazy[node] += value;
  51.         Push(node, l, r);
  52.         return;
  53.     }
  54.  
  55.     int mid = (l + r) / 2;
  56.  
  57.     update(2 * node, l, mid, wl, wr, value);
  58.     update(2 * node + 1, mid + 1, r, wl, wr, value);
  59.  
  60.     segTree[node] = segTree[2 * node] + segTree[2 * node + 1];
  61. } 
  62.  
  63. long long getSUM(int node, int l, int r, int wl, int wr) {
  64.     Push(node, l, r);
  65.     if(l > wr || r < wl) return 0;
  66.     if(wl <= l && r <= wr) return segTree[node];
  67.  
  68.     int mid = (l + r) / 2;
  69.     int s1 = getSUM(2 * node, l, mid, wl, wr);
  70.     int s2 = getSUM(2 * node + 1, mid + 1, r, wl, wr);
  71.  
  72.     return s1 + s2;
  73. }
  74.  
  75. void dfs(int u, int pa) {
  76.     Size[u] = 1;
  77.     depth[u] = (pa == -1 ? 0 : depth[pa] + 1);
  78.     parent[u] = pa;
  79.     heavy[u] = -1;
  80.     int numnode = 0;
  81.  
  82.     for(int v : adj[u]) {
  83.         if(v == pa) continue;
  84.         dfs(v, u);
  85.         Size[u] += Size[v];
  86.         if(maximize(numnode, Size[v])) {
  87.             heavy[u] = v;
  88.         }
  89.     }
  90. }
  91.  
  92. void HLD(int u, int h) {
  93.     head[u] = h;
  94.     pos[u] = ++timeDFS;
  95.  
  96.     if(heavy[u] != -1) {
  97.         HLD(heavy[u], h);
  98.     }
  99.  
  100.     for(int v : adj[u]) {
  101.         if(v == parent[u] || v == heavy[u]) continue;
  102.         HLD(v, v);
  103.     }
  104. }
  105.  
  106. void add_path(int u, int v) {
  107.     while(head[u] != head[v]) {
  108.         if(depth[head[u]] < depth[head[v]]) swap(u, v);
  109.         update(1, 1, n, pos[head[u]], pos[u], 1);
  110.  
  111.         u = parent[head[u]];
  112.     }
  113.  
  114.     if(depth[u] > depth[v]) swap(u, v);
  115.     update(1, 1, n, pos[u], pos[v], 1);
  116. }
  117.  
  118. long long getPath(int x) {
  119.     int u = edges[x].first;
  120.     int v = edges[x].second;
  121.     int node = (depth[u] > depth[v] ? v : u);
  122.     return getSUM(1, 1, n, pos[node], pos[node]);
  123. }
  124.  
  125. void Init() {
  126.     cin >> n >> q;
  127.  
  128.     for(int i = 1; i <= n - 1 ; i++) {
  129.         int u, v;
  130.         cin >> u >> v;
  131.         adj[u].push_back(v);
  132.         adj[v].push_back(u);
  133.         edges.push_back({u, v});
  134.     }
  135.  
  136.     dfs(1, -1);
  137.     HLD(1, 1);
  138.  
  139.     while(q--) {
  140.         int choose;
  141.         cin >> choose;
  142.         if(choose == 1) {
  143.             int u, v;
  144.             cin >> u >> v;
  145.             add_path(u, v);
  146.         } else {
  147.             int x;
  148.             cin >> x;
  149.             cout << getPath(x) << xd;
  150.         }
  151.     }
  152. }
  153.  
  154. signed main() {
  155.     HuuThien();
  156.     Init();
  157. }
Success #stdin #stdout 0.01s 10556KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/droayp
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!