import sys
input = sys.stdin.readline
maxn, logn = 10**5 + 7, 19
class Query:
def __init__(self, a = 0, b = 0, c = 0):
self.a, self.b, self.c = a, b, c
class Fenwick_tree:
def __init__(self, n):
self.n = n
self.bit = [0] * n
def update(self, x, val):
while(x <= self.n):
self.bit[x] += val
x += x & -x
def get(self, x):
res = 0
while(x):
res += self.bit[x]
x -= x & -x
return res
lv, par, timeIn, timeOut, dp = [0] * maxn, [0] * maxn, [0] * maxn, [0] * maxn, [0] * maxn
adj, road = [[] for i in range(maxn)], [[] for i in range(maxn)]
f= [[0 for i in range(logn)] for j in range(maxn)]
q = [Query()] * maxn
bit, nVisit = Fenwick_tree(maxn), 0
def dfs(u, p):
global nVisit
nVisit += 1
f[u][0], par[u], timeIn[u] = p, p, nVisit
for i in range(1, logn):
v = f[u][i - 1]
f[u][i] = -1 if(v == -1) else f[v][i - 1]
for v in adj[u]:
if(v != p):
lv[v] = lv[u] + 1
dfs(v, u)
timeOut[u] = nVisit
def jump(u, k):
cur = 0
while(k):
if(k & 1):
u = f[u][cur]
cur += 1
k >>= 1
return u
def lca(u, v):
if(lv[v] < lv[u]):
u, v = v, u
v = jump(v, lv[v] - lv[u])
if(u == v):
return u
for i in reversed(range(logn)):
if(f[u][i] != f[v][i]):
u, v = f[u][i], f[v][i]
return par[u]
def solve(u, p):
sumChild = 0
for v in adj[u]:
if(v != p):
solve(v, u)
sumChild += dp[v]
dp[u] = sumChild
for i in road[u]:
dp[u] = max(dp[u], sumChild - bit.get(timeIn[q[i].a]) - bit.get(timeIn[q[i].b]) + q[i].c)
bit.update(timeIn[u], dp[u] - sumChild)
bit.update(timeOut[u] + 1, sumChild - dp[u])
n = int(input())
for i in range(1, n):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
dfs(1, -1)
m = int(input())
for i in range(m):
a, b, c = map(int, input().split())
q[i] = Query(a, b, c)
road[lca(q[i].a, q[i].b)].append(i)
solve(1, -1)
print(dp[1])
Compilation message
election_campaign.cpp:1:1: error: 'import' does not name a type; did you mean 'short'?
import sys
^~~~~~
short
