This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#define FILE_IO
typedef long long LL;
const int NMAX = 1e5;
const int LG = 17;
typedef pair<int, int> pii;
LL dp[NMAX + 5], dp0[NMAX + 5];
int N, M;
int h[NMAX + 5], f[NMAX + 5];
int I, itv[NMAX + 5][2], lg2[2 * NMAX + 5], rmq[LG + 1][2 * NMAX + 5];
int cost[NMAX + 5];
pii path[NMAX + 5];
vector<int> edg[NMAX + 5], pth[NMAX + 5];
class BinaryIndexedTree
{
public:
int N;
LL aib[2 * NMAX + 5];
void U(int pos, int val)
{
for(; pos <= N; pos += (pos & (-pos)))
aib[pos] += val;
}
LL Q(int pos)
{
LL ans = 0;
for(; pos > 0; pos -= (pos & (-pos)))
ans += aib[pos];
return ans;
}
}sumdp, sumdp0;
void DFS(int nod, int fth)
{
f[nod] = fth;
h[nod] = h[fth] + 1;
itv[nod][0] = ++I;
rmq[0][I] = nod;
for(auto nxt: edg[nod])
if(nxt != fth)
DFS(nxt, nod);
itv[nod][1] = ++I;
rmq[0][I] = nod;
}
int minh(int a, int b) { if(h[a] < h[b]) return a; return b; }
int LCA(int a, int b)
{
int pa = itv[a][0], pb = itv[b][0];
if(pa > pb) swap(a, b), swap(pa, pb);
if(itv[a][0] <= itv[b][0] && itv[b][1] <= itv[a][1]) return a;
int pw = lg2[pb - pa + 1];
int nod = minh(rmq[pw][pa], rmq[pw][pb - (1 << pw) + 1]);
return f[nod];
}
void solve(int nod)
{
for(auto nxt: edg[nod])
if(nxt != f[nod])
{
solve(nxt);
dp0[nod] += dp[nxt];
}
sumdp0.U(itv[nod][0], dp0[nod]);
sumdp0.U(itv[nod][1], -dp0[nod]);
dp[nod] = dp0[nod];
for(auto id: pth[nod])
{
int x = path[id].first, y = path[id].second;
LL val = cost[id] + dp0[nod];
val += sumdp0.Q(itv[x][0]) - sumdp0.Q(itv[nod][0]);
val += sumdp0.Q(itv[y][0]) - sumdp0.Q(itv[nod][0]);
val -= sumdp.Q(itv[x][0]) - sumdp.Q(itv[nod][0]);
val -= sumdp.Q(itv[y][0]) - sumdp.Q(itv[nod][0]);
dp[nod] = max(dp[nod], val);
}
sumdp.U(itv[nod][0], dp[nod]);
sumdp.U(itv[nod][1], -dp[nod]);
}
int main()
{
#ifdef FILE_IO
freopen("1.in", "r", stdin);
//freopen("1.out", "w", stdout);
#endif
scanf("%d", &N);
for(int i = 1; i < N; i++)
{
int x, y;
scanf("%d%d", &x, &y);
edg[x].push_back(y);
edg[y].push_back(x);
}
DFS(1, 0);
for(int i = 2; i <= I; i++) lg2[i] = lg2[i >> 1] + 1;
for(int i = 1; (1 << i) <= I; i++)
for(int j = 1; j + (1 << i) - 1 <= I; j++)
rmq[i][j] = minh(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
scanf("%d", &M);
for(int i = 1; i <= M; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
path[i] = {a, b};
cost[i] = c;
pth[LCA(a, b)].push_back(i);
}
sumdp.N = I, sumdp0.N = I;
solve(1);
printf("%d\n", dp[1]);
return 0;
}
Compilation message (stderr)
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:130:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'LL {aka long long int}' [-Wformat=]
printf("%d\n", dp[1]);
~~~~~^
election_campaign.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
election_campaign.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
election_campaign.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &M);
~~~~~^~~~~~~~~~
election_campaign.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |