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)
- int solve();
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- solve();
- return 0;
- }
- struct item
- {
- int x, c;
- item() {};
- item(int x, int c) : x(x), c(c) {};
- };
- const int INF = 1e9 + 7;
- const int MAXN = 15e4 + 7;
- struct SegmentTree
- {
- struct Node
- {
- int x, add, id;
- Node() {};
- Node(int x, int add, int id) : x(x), add(add), id(id) {};
- };
- vector<Node> t;
- SegmentTree() { t.resize(600107); };
- Node max(Node &a, Node &b)
- {
- if (a.x > b.x)
- return a;
- return b;
- }
- 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, int id)
- {
- push(v, tl, tr);
- if (tl > r || tr < l)
- return;
- if (l <= tl && tr <= r)
- {
- t[v].add += val;
- if (id != -1)
- t[v].id = id;
- push(v, tl, tr);
- return;
- }
- int tm = tl + tr >> 1;
- update(2 * v + 1, tl, tm, l, r, val, id);
- update(2 * v + 2, tm + 1, tr, l, r, val, id);
- t[v] = max(t[2 * v + 1], t[2 * v + 2]);
- }
- };
- int solve()
- {
- int n;
- cin >> n;
- vector<vi> g(n);
- int r0 = -1, r1 = -1;
- for (int i = 0; i < n - 1; ++i)
- {
- int x, y;
- cin >> x >> y;
- --x, --y;
- if (!i)
- r0 = x, r1 = y;
- g[x].inb(y);
- g[y].inb(x);
- }
- int m;
- cin >> m;
- vector<vector<item>> q(n);
- int ans = 0;
- for (int i = 0; i < m; ++i)
- {
- int x, y, c;
- cin >> x >> y >> c;
- --x, --y;
- q[x].inb(item(y, c)), q[y].inb(item(x, c));
- }
- vi l(n, INF), r(n);
- vi was(n), was1(n);
- SegmentTree T;
- function<void(int, int, int&, int&)> dfsEU = [&](int u, int pr, int &id, int &sum)
- {
- was[u] = 2;
- was1[u] = 1;
- int add = 0;
- for (auto &x : q[u])
- {
- if (was1[x.x])
- add += x.c;
- }
- sum += add;
- if (g[u].size() == 1)
- {
- l[u] = id;
- r[u] = id;
- T.update(0, 0, MAXN - 1, id, id, sum, u);
- ++id;
- }
- for (int to : g[u])
- {
- if (to == pr)
- continue;
- dfsEU(to, u, id, sum);
- l[u] = min(l[u], l[to]);
- r[u] = max(r[u], r[to]);
- }
- //cout << u + 1 << " " << sum << " " << l[u] << " " << r[u] << "\n";
- was1[u] = 0;
- sum -= add;
- };
- int cnt = 0;
- int sum = 0;
- dfsEU(r0, r1, cnt, sum);
- int res = 0, id0 = r0, id1 = r1;
- function<void(int, int, int&)> dfsAns = [&](int u, int pr, int &sum)
- {
- int add = 0;
- was1[u] = 1;
- for (auto &x : q[u])
- {
- if (was1[x.x])
- add += x.c;
- if (was[x.x] == 2)
- T.update(0, 0, MAXN - 1, l[x.x], r[x.x], x.c, -1);
- }
- sum += add;
- //cout << u << " " << sum << " " << add << "\n";
- if (T.t[0].x + sum > res)
- {
- id0 = T.t[0].id + 1;
- id1 = u + 1;
- res = sum + T.t[0].x;
- }
- for (int to : g[u])
- {
- if (to == pr)
- continue;
- dfsAns(to, u, sum);
- }
- sum -= add;
- was1[u] = 0;
- for (auto &x : q[u])
- {
- if (was[x.x] == 2)
- T.update(0, 0, MAXN - 1, l[x.x], r[x.x], -x.c, -1);
- }
- };
- dfsAns(r1, r0, sum);
- cout << id0 << " " << id1 << " " << res + ans << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement