Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- #define X first
- #define Y second
- #define inb push_back
- #define mk make_pair
- #define all(v) v.begin(), v.end()
- #define sqr(x) (x) * (x)
- #define y1 zapadupal
- int solve();
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- solve();
- return 0;
- }
- struct Query
- {
- int l, r, val;
- Query() {};
- Query(int l, int r, int val) : l(l), r(r), val(val) {};
- };
- struct SegmentTree
- {
- struct Node
- {
- int x, add, id;
- Node() { x = 0, add = 0, id = 0; };
- Node(int x, int id) : x(x), add(0), id(id) {};
- };
- vector<Node> t;
- SegmentTree() {};
- SegmentTree(int n)
- {
- t.resize(4 * n);
- build(0, 0, n - 1);
- }
- Node max(Node &a, Node &b)
- {
- if (a.x > b.x)
- return a;
- return b;
- }
- void build(int v, int tl, int tr)
- {
- if (tl == tr)
- {
- t[v].id = tl;
- return;
- }
- int tm = tl + tr >> 1;
- build(2 * v + 1, tl, tm);
- build(2 * v + 2, tm + 1, tr);
- }
- void push(int v, int tl, int tr)
- {
- if (!t[v].add)
- return;
- t[v].x += t[v].add;
- if (tl != tr)
- {
- t[2 * v + 1].add += t[v].add;
- t[2 * v + 2].add += t[v].add;
- }
- t[v].add = 0;
- }
- void update(int v, int tl, int tr, int l, int r, int val)
- {
- push(v, tl, tr);
- if (tl > r || tr < l)
- return;
- if (l <= tl && tr <= r)
- {
- t[v].add += val;
- push(v, tl, tr);
- return;
- }
- int tm = tl + tr >> 1;
- update(2 * v + 1, tl, tm, l, r, val);
- update(2 * v + 2, tm + 1, tr, l, r, val);
- t[v] = max(t[2 * v + 1], t[2 * v + 2]);
- }
- };
- int solve()
- {
- int n;
- scanf("%d", &n);
- vector<vi> g(n);
- for (int i = 0; i < n - 1; ++i)
- {
- int x, y;
- scanf("%d %d", &x, &y);
- --x, --y;
- g[x].inb(y);
- g[y].inb(x);
- }
- vi tin(n), tout(n);
- vi tr(n);
- vector<vi> sons(n);
- int timer = -1;
- function<void(int, int)> dfs = [&](int u, int pr)
- {
- ++timer;
- tin[u] = timer;
- tr[timer] = u;
- for (int to : g[u])
- {
- if (to == pr)
- continue;
- sons[u].inb(to);
- dfs(to, u);
- }
- tout[u] = timer;
- };
- dfs(0, -1);
- int m;
- scanf("%d", &m);
- vector<vector<Query>> q(n + 2);
- for (int i = 0; i < m; ++i)
- {
- int x, y, val;
- scanf("%d %d %d", &x, &y, &val);
- --x, --y;
- if (tin[y] <= tin[x] && tin[x] <= tout[y])
- swap(x, y);
- if (tin[x] <= tin[y] && tin[y] <= tout[x])
- {
- int l = 0, r = sons[x].size();
- while (r - l > 1)
- {
- int mid = l + r >> 1;
- if (tin[sons[x][mid]] <= y)
- l = mid;
- else
- r = mid;
- }
- int s = sons[x][l];
- //0 <= tin[a] < tin[s]
- //tin[y] <= tin[b] <= tout[y]
- q[0].inb(Query(tin[y], tout[y], val));
- q[tin[s]].inb(Query(tin[y], tout[y], -val));
- //tout[s] < tin[a] <= timer
- //tin[y] <= tin[b] <= tout[y]
- q[tout[s] + 1].inb(Query(tin[y], tout[y], val));
- q[timer + 1].inb(Query(tin[y], tout[y], -val));
- }
- else
- {
- //tin[x] <= tin[a] <= tout[x]
- //tin[y] <= tin[b] <= tout[y]
- q[tin[x]].inb(Query(tin[y], tout[y], val));
- q[tout[x] + 1].inb(Query(tin[y], tout[y], -val));
- }
- }
- int ansx = 0, ansy = 0, ans = 0;
- SegmentTree T(n);
- for (int i = 0; i < n; ++i)
- {
- for (auto &cur : q[i])
- {
- T.update(0, 0, n - 1, cur.l, cur.r, cur.val);
- }
- int id = T.t[0].id;
- int c = T.t[0].x;
- if (c > ans)
- ansx = tr[i] + 1, ansy = id + 1, ans = c;
- }
- printf("%d %d %d\n", ansx, ansy, ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement