幻想乡大作战 [unfinished]

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100010;

struct Edge {
    int v, w;
    Edge* next;
};

int n, m, ql, qr, etotal, root;
int que[N], sum[N], mex[N], prt[N], emex[N], esum[N];
bool vis[N], cut[N];
Edge* g[N];

void addEdge(int u, int v, int w);
void order(int u, int from);
void bfs(int u);

int main() {
    scanf("%d%d", &n, &m);
    for (int rep = 1; rep < n; ++rep) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    memset(vis, 0, sizeof(vis));
    order(1, 0);
    while (m--) {
        int u, e;
        scanf("%d%d", &u, &e);
        etotal += e;
        while (u) {
            esum[u] += e;
            if (prt[u]) {
                if (esum[emex[prt[u]]] < esum[u])
                    emex[prt[u]] = u;
            }
            u = prt[u];
        }
        u = root;
        ll ans = 0;
        while (emex[u] && esum[emex[u]] * 2 >= etotal) {
            u = emex[u];
        }
    }
    return 0;
}

void bfs(int u) {
    que[ql = 0] = u;
    qr = 1;
    while (ql < qr) {
        u = que[ql++];
        vis[u] = true;
        for (Edge* p = g[u]; p; p = p->next)
            if (!vis[p->v] && !cut[p->v])
                que[qr++] = p->v;
    }
}

void order(int u, int from) {
    bfs(u);
    int div = que[qr - 1];
    for (int i = qr - 1; i >= 0; --i) {
        u = que[i];
        vis[u] = false;
        sum[u] = 1;
        mex[u] = 0;
        for (Edge* p = g[u]; p; p = p->next)
            if (!vis[p->v] && !cut[p->v]) {
                sum[u] += sum[p->v];
                mex[u] = max(mex[u], sum[p->v]);
            }
        mex[u] = max(mex[u], qr - sum[u]);
        if (mex[u] < mex[div])
            div = u;
    }
    cut[div] = true;
    prt[div] = from;
    if (from == 0)
        root = div;
    for (Edge* p = g[div]; p; p = p->next)
        if (!cut[p->v])
            order(p->v, div);
}

void addEdge(int u, int v, int w) {
    static Edge pool[N * 2];
    static Edge* p = pool;
    p->v = v;
    p->w = w;
    p->next = g[u];
    g[u] = p;
    ++p;
}