// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
if (sz(s))
{
freopen((s + ".in").c_str(), "r", stdin);
if (s != "test1")
freopen((s + ".out").c_str(), "w", stdout);
}
#endif
}
const int MAX = 100005, SZ = 20;
int n, m, depth[MAX];
vi adj[MAX];
vector<pair<pii, int>>queries[MAX];
ll a[MAX], dp[MAX];
template<int SZ>struct hld
{
struct item
{
ll sum;
};
item single(ll i)
{
return { i };
}
item merge(item x, item y)
{
item ans;
ans.sum = x.sum + y.sum;
return ans;
}
vector<item> tree;
vector<item>A;
int height;
item neutral = { 0 };
void build(vector<item>& A, int v, int tl, int tr)
{
if (tl == tr)
tree[v] = A[tl];
else
{
int mid = (tl + tr) / 2;
build(A, 2 * v + 1, tl, mid);
build(A, 2 * v + 2, mid + 1, tr);
tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
}
}
void build(vll& B)
{
int n = B.size();
height = log2(n + 1) + 1;
A.rsz(n);
tree.rsz((1 << height + 1) - 1);
F0R(i, n)A[i] = single(B[i]);
A.rsz(1 << height, neutral);
build(A, 0, 0, (1 << height) - 1);
}
item query(int v, int tl, int tr, int l, int r)
{
if (r<tl || l>tr)return neutral;
if (l <= tl && r >= tr)
{
return tree[v];
}
int mid = (tl + tr) / 2;
return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r));
}
ll query(int l, int r)
{
return query(0, 0, (1 << height) - 1, l, r).sum;
}
void update(int v, int tl, int tr, int pos, item val)
{
if (tl == tr)
{
tree[v] = val;
}
else
{
int mid = (tl + tr) / 2;
if (pos <= mid)
update(2 * v + 1, tl, mid, pos, val);
else
update(2 * v + 2, mid + 1, tr, pos, val);
tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
}
}
void update(int pos, ll val)
{
update(0, 0, (1 << height) - 1, pos, single(val));
}
vi label, sizes, depth, heavy_child, parent, head, dist;
vector<vi>jump;
int get(int a, int b)
{
F0R(j, SZ)
{
if (b & (1 << j))
{
a = jump[a][j];
}
}
return a;
}
int LCA(int a, int b)
{
if (depth[a] < depth[b])swap(a, b);
a = get(a, depth[a] - depth[b]);
if (a == b)return a;
int j = SZ;
while (j)
{
j--;
int ta = jump[a][j], tb = jump[b][j];
if (ta != tb)a = ta, b = tb;
}
return parent[a];
}
void dfs0(int i, int p)
{
parent[i] = p;
sizes[i] = 1;
trav(x, adj[i])
{
if (x == p)continue;
depth[x] = depth[i] + 1;
dfs0(x, i);
sizes[i] += sizes[x];
}
}
int cur = 0;
void dfs1(int i, int p)
{
label[i] = cur++;
if (heavy_child[i] != -1)
{
head[heavy_child[i]] = head[i];
dfs1(heavy_child[i], i);
dist[i] = 1 + dist[heavy_child[i]];
}
trav(x, adj[i])
{
if (x != heavy_child[i] && x != p)
{
head[x] = x;
dfs1(x, i);
}
}
}
void init()
{
sizes.rsz(n);
depth.rsz(n);
parent.rsz(n);
dfs0(0, -1);
jump.rsz(n, vi(SZ));
F0R(i, n)jump[i][0] = parent[i];
F0R(i, SZ - 1)
{
F0R(j, n)jump[j][i + 1] = (jump[j][i] == -1 ? -1 : jump[jump[j][i]][i]);
}
heavy_child.rsz(n);
F0R(i, n)
{
vpi t;
trav(x, adj[i])if (parent[i] != x)t.pb({ sizes[x],x });
sort(all(t), greater<pii>());
if (sz(t))heavy_child[i] = t[0].s;
else heavy_child[i] = -1;
}
label.rsz(n);
head.rsz(n);
dist.rsz(n);
dfs1(0, -1);
vll t(n);
F0R(i, n)t[label[i]] = a[i];
build(t);
}
ll solve(int x, int l)// find the sum of the values from x to l excluding l.
{
ll ans = 0;
while (1)
{
if (x == l)return ans;
if (head[x] == x)
{
ans += a[x];
x = parent[x];
continue;
}
int h = head[x];
if (depth[h] > depth[l])
{
ans += query(label[h], label[x]);
x = parent[h];
continue;
}
ans += query(label[l] + 1, label[x]);
x = l;
}
return ans;
}
ll query_path(int x, int y)
{
int l = LCA(x, y);
return solve(x, l) + solve(y, l) + a[l];
}
void update_path(int x, int y)
{
a[x] = y;
update(label[x], y);
}
};
hld<SZ>g;
void dfs(int i, int p = -1)
{
ll sum = 0;
trav(x, adj[i])
{
if (x == p)continue;
depth[x] = depth[i] + 1;
dfs(x, i);
dp[i] = max(dp[i], dp[x]);
sum += dp[x];
}
trav(x, queries[i])
{
int l = i;
ll val = 0;
if (l == x.f.f)swap(x.f.f, x.f.s);
if (l == x.f.s)
{
val = g.query_path(g.get(x.f.f, depth[x.f.f] - depth[l] - 1), x.f.f) + x.s + sum;
}
else
{
val = g.query_path(g.get(x.f.f, depth[x.f.f] - depth[l] - 1), x.f.f) + g.query_path(x.f.s, g.get(x.f.s, depth[x.f.s] - depth[l] - 1)) + x.s + sum;
}
dp[i] = max(dp[i], val);
}
trav(x, adj[i])
{
if (x == p)continue;
a[i] += dp[x];
}
a[i] -= dp[i];
g.update_path(i, a[i]);
}
int main()
{
setIO("test1");
cin >> n;
F0R(i, n - 1)
{
int x, y;
cin >> x >> y;
adj[--x].pb(--y);
adj[y].pb(x);
}
g.init();
cin >> m;
F0R(i, m)
{
int x, y, z;
cin >> x >> y >> z;
int l = g.LCA(--x, --y);
queries[l].pb({ {x,y},z });
}
dfs(0);
cout << dp[0] << endl;
}
Compilation message
election_campaign.cpp: In instantiation of 'void hld<SZ>::build(vll&) [with int SZ = 20; vll = std::vector<long long int>]':
election_campaign.cpp:221:3: required from 'void hld<SZ>::init() [with int SZ = 20]'
election_campaign.cpp:305:9: required from here
election_campaign.cpp:97:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
97 | tree.rsz((1 << height + 1) - 1);
| ~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4916 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5000 KB |
Output is correct |
| 3 |
Correct |
5 ms |
4940 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5196 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5452 KB |
Output is correct |
| 4 |
Correct |
270 ms |
57132 KB |
Output is correct |
| 5 |
Correct |
266 ms |
57364 KB |
Output is correct |
| 6 |
Correct |
213 ms |
57168 KB |
Output is correct |
| 7 |
Correct |
269 ms |
57100 KB |
Output is correct |
| 8 |
Correct |
262 ms |
57176 KB |
Output is correct |
| 9 |
Correct |
226 ms |
57124 KB |
Output is correct |
| 10 |
Correct |
275 ms |
57140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5452 KB |
Output is correct |
| 4 |
Correct |
270 ms |
57132 KB |
Output is correct |
| 5 |
Correct |
266 ms |
57364 KB |
Output is correct |
| 6 |
Correct |
213 ms |
57168 KB |
Output is correct |
| 7 |
Correct |
269 ms |
57100 KB |
Output is correct |
| 8 |
Correct |
262 ms |
57176 KB |
Output is correct |
| 9 |
Correct |
226 ms |
57124 KB |
Output is correct |
| 10 |
Correct |
275 ms |
57140 KB |
Output is correct |
| 11 |
Correct |
23 ms |
6220 KB |
Output is correct |
| 12 |
Correct |
268 ms |
57412 KB |
Output is correct |
| 13 |
Correct |
293 ms |
57480 KB |
Output is correct |
| 14 |
Correct |
206 ms |
57472 KB |
Output is correct |
| 15 |
Correct |
253 ms |
57436 KB |
Output is correct |
| 16 |
Correct |
207 ms |
57368 KB |
Output is correct |
| 17 |
Correct |
292 ms |
57412 KB |
Output is correct |
| 18 |
Correct |
266 ms |
57412 KB |
Output is correct |
| 19 |
Correct |
213 ms |
57396 KB |
Output is correct |
| 20 |
Correct |
252 ms |
57488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
407 ms |
31920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4916 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5000 KB |
Output is correct |
| 3 |
Correct |
5 ms |
4940 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5196 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4916 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5000 KB |
Output is correct |
| 3 |
Correct |
5 ms |
4940 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5196 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
