#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e3 + 9;
const ll mod = 1e9 + 7;
const ll Log2 = 20;
typedef pair<ll,ll> LL;
vector<ll> g[N],Q[N];
ll n,m,x,y,All[N],dp[N];
struct plan{
ll x,y,cost;
};
plan q[N];
ll par[N][Log2],d[N],ans,child[N];
void DFS(ll u,ll p){
child[u] = 1;
for (ll i = 1;i < Log2;i++) if ((1 << i) <= d[u])
par[u][i] = par[par[u][i - 1]][i - 1];
for (auto i : g[u]){
if (i == p) continue;
par[i][0] = u; d[i] = d[u] + 1; DFS(i,u);
child[u] += child[i];
}
}
ll LCA(ll u,ll v){
if (d[u] > d[v]) swap(u,v);
for (ll i = Log2 - 1;i >= 0;i--) if ((1 << i) <= d[v] && d[par[v][i]] >= d[u])
v = par[v][i];
if (u == v) return u;
for (ll i = Log2 - 1;i >= 0;i--) if (par[v][i] != par[u][i])
v = par[v][i],u = par[u][i];
return par[u][0];
}
ll st[4*N];
void upd(ll id,ll l,ll r,ll u,ll val){
if (u < l||r < u) return;
if (l == r){
st[id] += val; return;
}
ll mid = (l + r)/2;
upd(id*2,l,mid,u,val); upd(id*2 + 1,mid + 1,r,u,val);
st[id] = st[id*2] + st[id*2 + 1];
}
ll Get(ll id,ll l,ll r,ll u,ll v){
if (v < l||r < u) return 0;
if (u <= l&&r <= v) return st[id];
ll mid = (l + r)/2;
return Get(id*2,l,mid,u,v) + Get(id*2 + 1,mid + 1,r,u,v);
}
ll pos[N],Real[N],chain[N],head[N],nTime = 1,cur = 1;
void DFShld(ll u,ll p){
pos[u] = nTime; Real[nTime] = u; nTime++;
if (!head[cur]) head[cur] = u; chain[u] = cur;
LL s = {0,0};
for (auto i : g[u]){
if (i == p) continue;
s = max(s,{child[i],i});
}
if (s.sc) DFShld(s.sc,u);
for (auto i : g[u]){
if (i == p || i == s.sc) continue;
cur++; DFShld(i,u);
}
}
ll hld(ll u,ll v){
/// u is par of v
ll res = 0;
while(chain[u] != chain[v]){
ll nxt = head[chain[v]];
res += Get(1,1,n,pos[nxt],pos[v]);
v = par[nxt][0];
}
res += Get(1,1,n,pos[u],pos[v]); return res;
}
void f(ll u){
for (auto i : g[u]) if (d[i] > d[u]) f(i),All[u] += dp[i];
upd(1,1,n,pos[u],All[u]); dp[u] = All[u];
for (auto i : Q[u]){
x = q[i].x; y = q[i].y; ll cost = q[i].cost;
dp[u] = max(dp[u],hld(u,x) + hld(u,y) - All[u] + cost);
}
upd(1,1,n,pos[u],-dp[u]); ans = max(ans,dp[u]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin>>n;
for (ll i = 1;i < n;i++){
cin>>x>>y;
g[x].push_back(y); g[y].push_back(x);
}
DFS(1,0); DFShld(1,0);
cin>>m;
for (ll i = 1;i <= m;i++){
cin>>q[i].x>>q[i].y>>q[i].cost;
if (d[q[i].x] > d[q[i].y]) swap(q[i].x,q[i].y);
ll now = LCA(q[i].x,q[i].y);
Q[now].push_back(i);
}
f(1); cout<<ans;
}
Compilation message
election_campaign.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
election_campaign.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
election_campaign.cpp: In function 'void DFShld(int, int)':
election_campaign.cpp:68:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
68 | if (!head[cur]) head[cur] = u; chain[u] = cur;
| ^~
election_campaign.cpp:68:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
68 | if (!head[cur]) head[cur] = u; chain[u] = cur;
| ^~~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
588 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
588 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
