Submission #206770

#	Time	Username	Problem	Language	Result	Execution time	Memory
206770		Kamisama	Election Campaign (JOI15_election_campaign)	Pypy 2	0 / 100	1026 ms	75024 KiB

election_campaign

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])

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40