Cod sursa(job #2132907)

Utilizator amaliarebAmalia Rebegea amaliareb Data 16 februarie 2018 11:19:53
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("regat.in");
ofstream g("regat.out");
const int MaxN = 100005;
struct miau{int l, r;} intv[MaxN];
int n, m, n2, ans[MaxN];
vector<miau> gr[MaxN], v;
vector<int> q[MaxN];
bitset<MaxN> viz;
struct AINT {
    int aint[4 * MaxN], lazy[4 * MaxN];

    AINT() {
        memset(aint, 0, sizeof(aint));
        memset(lazy, 0, sizeof(lazy));
    }

    inline void propag(int node, int l, int r) {
        if (!lazy[node]) return;
        aint[node] += lazy[node];
        if (l != r) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    void update(int node, int l, int r, int ql, int qr, int val) {
        if (l >= ql && r <= qr) {
            lazy[node] += val;
            propag(node, l, r);
            return;
        }
        propag(node, l, r);
        if (l <= qr && r >= ql) {
            int mid = (l + r) / 2;
            update(2 * node, l, mid, ql, qr, val);
            update(2 * node + 1, mid + 1, r, ql, qr, val);
            aint[node] = max(aint[2 * node], aint[2 * node + 1]);
        }
    }

    int findpoz(int node, int l, int r) {
        propag(node, l, r);
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (aint[2 * node] + lazy[2 * node] == aint[node])
            return findpoz(2 * node, l, mid);
        return findpoz(2 * node + 1, mid + 1, r);
    }

} aint;

void dfs1(int node, int cost) {
    viz[node] = 1;
    intv[node].l = ++n2;
    aint.update(1, 1, n, n2, n2, cost);
    for (auto son: gr[node]) {
        if (!viz[son.l]) {
            dfs1(son.l, cost + son.r);
        }
    }
    intv[node].r = n2;
}

inline void muta(int a, int cost) {
    int l = intv[a].l, r = intv[a].r;
    aint.update(1, 1, n, l, r, -cost);
    if (l > 1) aint.update(1, 1, n, 1, l - 1, cost);
    if (r < n) aint.update(1, 1, n, r + 1, n, cost);
}

void dfs(int node) {
    viz[node] = 1;
    reverse(q[node].begin(), q[node].end());
    while (!q[node].empty()) {
        int x = q[node].back(), pozz = aint.findpoz(1, 1, n);
        ans[x] = aint.aint[1];
        v.push_back({ans[x], pozz});
        aint.update(1, 1, n, pozz, pozz, -ans[x]);
        q[node].pop_back();
    }
    while (!v.empty()) {
        int val = v.back().l, pozz = v.back().r;
        aint.update(1, 1, n, pozz, pozz, val);
        v.pop_back();
    }
    for (auto son: gr[node]) {
        if (!viz[son.l]) {
            muta(son.l, son.r);
            dfs(son.l);
            muta(son.l, -son.r);
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1; i < n; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        gr[x].push_back({y, c});
        gr[y].push_back({x, c});
    }
    dfs1(1, 0);
    viz.reset();
    for (int i = 1; i <= m; ++i) {
        int x;
        f >> x;
        q[x].push_back(i);
    }
    dfs(1);
    for (int i = 1; i <= m; ++i) g << ans[i] << '\n';
    return 0;
}