Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define f first
- #define s second
- using namespace std;
- typedef long long ll;
- typedef pair <int, int> pii;
- typedef vector <int> vi;
- typedef vector < vector <int> > vvi;
- int rnd(){
- return ((rand() << 15) + rand());
- }
- struct node{
- node *l, *r;
- ll x;
- int y, val, mx;
- node(ll cur_x, int cur_val): l(nullptr), r(nullptr), x(cur_x), y(rnd()), val(cur_val), mx(cur_val){}
- void print(){
- if(l != nullptr)l->print();
- cout << x << ' ' << mx << '\n';
- if(r != nullptr)r->print();
- }
- };
- void upd(node *& t){
- if(t == nullptr)return;
- t->mx = t->val;
- if(t->l != nullptr)
- t->mx = max(t->mx, t->l->mx);
- if(t->r != nullptr)
- t->mx = max(t->mx, t->r->mx);
- }
- pair <node*, node*> split(node *t, ll key){
- if(t == nullptr)return {nullptr, nullptr};
- if(t->x <= key){
- pair <node*, node*> sp = split(t->r, key);
- t->r = sp.f;
- upd(t);
- upd(sp.s);
- return {t, sp.s};
- }
- else{
- pair <node*, node*> sp = split(t->l, key);
- t->l = sp.s;
- upd(t);
- upd(sp.f);
- return {sp.f, t};
- }
- }
- node *merge(node *a, node *b){
- if(a == nullptr)return b;
- if(b == nullptr)return a;
- if(a->y < b->y){
- a->r = merge(a->r, b);
- upd(a);
- return a;
- }
- else{
- b->l = merge(a, b->l);
- upd(b);
- return b;
- }
- }
- node *ins(node *& t, ll v, int cur_val){
- pair <node*, node*> sp = split(t, v);
- return merge(merge(sp.f, new node(v, cur_val)), sp.s);
- }
- int query(node *& t, ll v){
- pair <node*, node*> sp = split(t, v);
- int ans = (sp.f == nullptr ? 0: sp.f->mx);
- t = merge(sp.f, sp.s);
- return ans;
- }
- int lg, timer;
- vvi p;
- vector < vector < pair <int, ll> > > g;
- vi sz, par, tin, tout, used;
- vector <ll> h;
- vector <node*> dd;
- void dfs0(int v, int curp){
- tin[v] = timer++;
- p[v][0] = curp;
- for(int i = 1; i < lg; i++)
- p[v][i] = p[p[v][i - 1]][i - 1];
- for(int i = 0; i < g[v].size(); i++){
- int to = g[v][i].f;
- if(to == curp)
- continue;
- h[to] = h[v] + g[v][i].s;
- dfs0(to, v);
- }
- tout[v] = timer++;
- }
- bool upper(int u, int v){
- return (tin[u] <= tin[v] && tout[u] >= tout[v]);
- }
- int lca(int u, int v){
- for(int i = lg - 1; i >= 0; i--)
- if(!upper(p[u][i], v))
- u = p[u][i];
- return p[u][0];
- }
- ll dist(int u, int v){
- return h[u] + h[v] - 2 * h[lca(u, v)];
- }
- void dfs(int v, int curp){
- sz[v] = 1;
- for(int i = 0; i < g[v].size(); i++){
- int to = g[v][i].f;
- if(to == curp || used[to])
- continue;
- dfs(to, v);
- sz[v] += sz[to];
- }
- }
- int find_centroid(int root, int v, int curp){
- int mx = -1;
- for(int i = 0; i < g[v].size(); i++){
- int to = g[v][i].f;
- if(to == curp || used[to])
- continue;
- if(sz[to] > sz[root] / 2 && (mx == -1 || sz[to] > sz[mx]))
- mx = to;
- }
- if(mx == -1)
- return v;
- return find_centroid(root, mx, v);
- }
- void centroid_decomposition(int v, int curp){
- dfs(v, -1);
- int cur = find_centroid(v, v, -1);
- par[cur] = curp;
- used[cur] = 1;
- for(int i = 0; i < g[cur].size(); i++){
- int to = g[cur][i].f;
- if(used[to])
- continue;
- centroid_decomposition(to, cur);
- }
- }
- void update(int ci, int di, int cur_val){
- dd[ci] = ins(dd[ci], di, cur_val);
- int v = par[ci];
- while(v != -1){
- dd[v] = ins(dd[v], di + dist(ci, v), cur_val);
- v = par[v];
- }
- }
- int get_max(int ci, int di){
- int ans = query(dd[ci], di);
- int v = par[ci];
- while(v != -1){
- ans = max(ans, query(dd[v], di - dist(ci, v)));
- v = par[v];
- }
- return ans;
- }
- signed main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- freopen("events.in", "r", stdin);
- freopen("events.out", "w", stdout);
- int n;
- cin >> n;
- lg = 0;
- while((1 << lg) < n)
- lg++;
- lg++;
- g.resize(n), sz.resize(n), par.resize(n), dd.resize(n, nullptr), h.resize(n),
- p.resize(n, vi(lg)), tin.resize(n), tout.resize(n), used.resize(n);
- for(int i = 0; i < n - 1; i++){
- int u, v, l;
- cin >> u >> v >> l;
- u--, v--;
- g[u].push_back({v, l});
- g[v].push_back({u, l});
- }
- dfs0(0, 0);
- centroid_decomposition(0, -1);
- int m;
- cin >> m;
- vector <pii> qs(m);
- vi dp(m);
- for(int i = 0; i < m; i++)
- cin >> qs[i].s >> qs[i].f, qs[i].s--;
- sort(qs.begin(), qs.end());
- dp[0] = 1;
- update(qs[0].s, qs[0].f, 1);
- for(int i = 1; i < m; i++){
- dp[i] = get_max(qs[i].s, qs[i].f) + 1;
- update(qs[i].s, qs[i].f, dp[i]);
- }
- cout << *max_element(dp.begin(), dp.end()) << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement