Advertisement
Guest User

Untitled

a guest
Jul 20th, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define f first
  3. #define s second
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair <int, int> pii;
  9. typedef vector <int> vi;
  10. typedef vector < vector <int> > vvi;
  11.  
  12. int rnd(){
  13.     return ((rand() << 15) + rand());
  14. }
  15.  
  16. struct node{
  17.     node *l, *r;
  18.     ll x;
  19.     int y, val, mx;
  20.     node(ll cur_x, int cur_val): l(nullptr), r(nullptr), x(cur_x), y(rnd()), val(cur_val), mx(cur_val){}
  21.     void print(){
  22.         if(l != nullptr)l->print();
  23.         cout << x << ' ' << mx << '\n';
  24.         if(r != nullptr)r->print();
  25.     }
  26. };
  27.  
  28. void upd(node *& t){
  29.     if(t == nullptr)return;
  30.     t->mx = t->val;
  31.     if(t->l != nullptr)
  32.         t->mx = max(t->mx, t->l->mx);
  33.     if(t->r != nullptr)
  34.         t->mx = max(t->mx, t->r->mx);
  35. }
  36.  
  37. pair <node*, node*> split(node *t, ll key){
  38.     if(t == nullptr)return {nullptr, nullptr};
  39.     if(t->x <= key){
  40.         pair <node*, node*> sp = split(t->r, key);
  41.         t->r = sp.f;
  42.         upd(t);
  43.         upd(sp.s);
  44.         return {t, sp.s};
  45.     }
  46.     else{
  47.         pair <node*, node*> sp = split(t->l, key);
  48.         t->l = sp.s;
  49.         upd(t);
  50.         upd(sp.f);
  51.         return {sp.f, t};
  52.     }
  53. }
  54.  
  55. node *merge(node *a, node *b){
  56.     if(a == nullptr)return b;
  57.     if(b == nullptr)return a;
  58.     if(a->y < b->y){
  59.         a->r = merge(a->r, b);
  60.         upd(a);
  61.         return a;
  62.     }
  63.     else{
  64.         b->l = merge(a, b->l);
  65.         upd(b);
  66.         return b;
  67.     }
  68. }
  69.  
  70. node *ins(node *& t, ll v, int cur_val){
  71.     pair <node*, node*> sp = split(t, v);
  72.     return merge(merge(sp.f, new node(v, cur_val)), sp.s);
  73. }
  74.  
  75. int query(node *& t, ll v){
  76.     pair <node*, node*> sp = split(t, v);
  77.     int ans = (sp.f == nullptr ? 0: sp.f->mx);
  78.     t = merge(sp.f, sp.s);
  79.     return ans;
  80. }
  81.  
  82. int lg, timer;
  83. vvi p;
  84. vector < vector < pair <int, ll> > > g;
  85. vi sz, par, tin, tout, used;
  86. vector <ll> h;
  87. vector <node*> dd;
  88.  
  89. void dfs0(int v, int curp){
  90.     tin[v] = timer++;
  91.     p[v][0] = curp;
  92.     for(int i = 1; i < lg; i++)
  93.         p[v][i] = p[p[v][i - 1]][i - 1];
  94.     for(int i = 0; i < g[v].size(); i++){
  95.         int to = g[v][i].f;
  96.         if(to == curp)
  97.             continue;
  98.         h[to] = h[v] + g[v][i].s;
  99.         dfs0(to, v);
  100.     }
  101.     tout[v] = timer++;
  102. }
  103.  
  104. bool upper(int u, int v){
  105.     return (tin[u] <= tin[v] && tout[u] >= tout[v]);
  106. }
  107.  
  108. int lca(int u, int v){
  109.     for(int i = lg - 1; i >= 0; i--)
  110.         if(!upper(p[u][i], v))
  111.             u = p[u][i];
  112.     return p[u][0];
  113. }
  114.  
  115. ll dist(int u, int v){
  116.     return h[u] + h[v] - 2 * h[lca(u, v)];
  117. }
  118.  
  119. void dfs(int v, int curp){
  120.     sz[v] = 1;
  121.     for(int i = 0; i < g[v].size(); i++){
  122.         int to = g[v][i].f;
  123.         if(to == curp || used[to])
  124.             continue;
  125.         dfs(to, v);
  126.         sz[v] += sz[to];
  127.     }
  128. }
  129.  
  130. int find_centroid(int root, int v, int curp){
  131.     int mx = -1;
  132.     for(int i = 0; i < g[v].size(); i++){
  133.         int to = g[v][i].f;
  134.         if(to == curp || used[to])
  135.             continue;
  136.         if(sz[to] > sz[root] / 2 && (mx == -1 || sz[to] > sz[mx]))
  137.             mx = to;
  138.     }
  139.  
  140.     if(mx == -1)
  141.         return v;
  142.     return find_centroid(root, mx, v);
  143. }
  144.  
  145. void centroid_decomposition(int v, int curp){
  146.     dfs(v, -1);
  147.     int cur = find_centroid(v, v, -1);
  148.     par[cur] = curp;
  149.     used[cur] = 1;
  150.     for(int i = 0; i < g[cur].size(); i++){
  151.         int to = g[cur][i].f;
  152.         if(used[to])
  153.             continue;
  154.         centroid_decomposition(to, cur);
  155.     }
  156. }
  157.  
  158. void update(int ci, int di, int cur_val){
  159.     dd[ci] = ins(dd[ci], di, cur_val);
  160.     int v = par[ci];
  161.     while(v != -1){
  162.         dd[v] = ins(dd[v], di + dist(ci, v), cur_val);
  163.         v = par[v];
  164.     }
  165. }
  166.  
  167. int get_max(int ci, int di){
  168.     int ans = query(dd[ci], di);
  169.     int v = par[ci];
  170.     while(v != -1){
  171.         ans = max(ans, query(dd[v], di - dist(ci, v)));
  172.         v = par[v];
  173.     }
  174.     return ans;
  175. }
  176.  
  177. signed main()
  178. {
  179.     ios_base::sync_with_stdio(0);
  180.     cin.tie(0);
  181.     freopen("events.in", "r", stdin);
  182.     freopen("events.out", "w", stdout);
  183.     int n;
  184.     cin >> n;
  185.     lg = 0;
  186.     while((1 << lg) < n)
  187.         lg++;
  188.     lg++;
  189.     g.resize(n), sz.resize(n), par.resize(n), dd.resize(n, nullptr), h.resize(n),
  190.     p.resize(n, vi(lg)), tin.resize(n), tout.resize(n), used.resize(n);
  191.     for(int i = 0; i < n - 1; i++){
  192.         int u, v, l;
  193.         cin >> u >> v >> l;
  194.         u--, v--;
  195.         g[u].push_back({v, l});
  196.         g[v].push_back({u, l});
  197.     }
  198.  
  199.     dfs0(0, 0);
  200.     centroid_decomposition(0, -1);
  201.  
  202.     int m;
  203.     cin >> m;
  204.     vector <pii> qs(m);
  205.     vi dp(m);
  206.     for(int i = 0; i < m; i++)
  207.         cin >> qs[i].s >> qs[i].f, qs[i].s--;
  208.     sort(qs.begin(), qs.end());
  209.     dp[0] = 1;
  210.     update(qs[0].s, qs[0].f, 1);
  211.     for(int i = 1; i < m; i++){
  212.         dp[i] = get_max(qs[i].s, qs[i].f) + 1;
  213.         update(qs[i].s, qs[i].f, dp[i]);
  214.     }
  215.     cout << *max_element(dp.begin(), dp.end()) << '\n';
  216.     return 0;
  217. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement