제출 #293529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293529		davooddkareshki	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	535 ms	41976 KiB

election_campaign

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

typedef long long ll;

const int maxn = 1e5+2;
const int mod = 1e9+7;
const int inf = 1e9+10;

vector<int> g[maxn];
int par[maxn][20], tin[maxn], st[maxn], tim, h[maxn], n, m;
void pfs(int v)
{
    for(int i = 1; (1<<i) <= h[v]; i++)
        par[v][i] = par[par[v][i-1]][i-1];

    tin[v] = ++tim;
    st[v] = 1;
    for(auto u : g[v])
        if(u != par[v][0])
        {
            par[u][0] = v;
            h[u] = h[v] + 1;
            pfs(u);
            st[v] += st[u];
        }
}

int get_par(int v, int he)
{
    int i = 0;
    while(he)
    {
        if(he&1) v = par[v][i];
        he >>= 1; i++;
    }
    return v;
}

int lca(int u, int v)
{
    if(h[u] > h[v]) swap(u,v);
    v = get_par(v,h[v]-h[u]);
    if(u == v) return v;

    for(int i = 19; i >= 0; i--)
        if(par[v][i] != par[u][i])
        {
            v = par[v][i];
            u = par[u][i];
        }
    return par[v][0];
}

struct fenwick
{
    int fen[maxn];

    void _add(int pos, int val)
    {
        for(; pos <= n; pos |= (pos+1))
            fen[pos] += val;
    }

    void add(int v, int val)
    {
        /// be zirderakht v val ta ezafe kon
        int l = tin[v], r = tin[v] + st[v] - 1;
        _add(l,val);
        _add(r+1,-val);
    }

    int qu(int v)
    {
        int pos = tin[v], res = 0;
        for(; pos >= 0; pos = (pos&(pos+1))-1)
            res += fen[pos];
        return res;
    }
} fen;

int dp[maxn];
vector<pair<pii,int>> Q[maxn];
void dfs(int v)
{
    int sum = 0;
    for(auto u : g[v])
        if(u != par[v][0])
        {
            dfs(u);
            sum += dp[u];
        }

    dp[v] = sum;
    for(auto e : Q[v])
    {
        int x = e.F.F, y = e.F.S, c = e.S;
        int ans = fen.qu(x) + fen.qu(y) - 2 * fen.qu(par[v][0]);
        /// (v = Root) ham check kon    x anc y ham chek kon
        ans -= sum;
        dp[v] = max(dp[v],ans+c);
    }
    fen.add(par[v][0],dp[v]);
    fen.add(v,-dp[v]);
}

signed main()
{
	//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>> n;
    for(int i = 1, u, v; i < n; i++)
    {
        cin>> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    pfs(1);
    cin>> m;
    for(int i = 1, x, y, c; i <= m; i++)
    {
        cin>> x >> y >> c;
        Q[lca(x,y)].push_back({{x,y},c});
    }
    dfs(1);
    cout<< dp[1];
}
/*
7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
5
7 5 4
5 8 9
4 3 9
1 3 3
2 8 11

10
10 6
2 7
1 9
9 8
3 8
6 4
7 8
5 4
4 8
7
1 3 1
4 10 1
2 8 1
5 3 1
3 7 1
8 5 1
1 9 1
*/

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