Untitled

mail@pastecode.io avatar
unknown
c_cpp
16 days ago
4.2 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#define Task "B"
#define ll long long
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define F first
#define S second
#define all(v) (v).begin(), (v).end()

typedef pair<int, int> ii;

const int N = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }

template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }

vector<ii> adj[N];
int child[N], par[N];
bool del[N];
vector<ll> distVals[N], parDist[N];
vector<int> cenAdj[N];

struct LCA {
    int par[N][20];
    ll dist[N];
    int high[N];

    void dfs(int u) {
        for (auto e : adj[u]) {
            int v = e.F, w = e.S;
            if (v == par[u][0]) continue;
            high[v] = high[u] + 1;
            dist[v] = dist[u] + w;
            par[v][0] = u;
            dfs(v);
        }
    }

    void setupLCA(int numNode) {
        dfs(1);
        FOR(i, 1, 17) FOR(u, 1, numNode)
            par[u][i] = par[par[u][i - 1]][i - 1];
        high[0] = -1;
    }

    int get(int u, int v) {
        if (high[u] < high[v]) return get(v, u);
        FOD(i, 17, 0) if (high[par[u][i]] >= high[v])
            u = par[u][i];
        if (u == v) return u;
        FOD(i, 17, 0) if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
        return par[u][0];
    }

    ll Dist(int u, int v) {
        return dist[u] + dist[v] - 2 * dist[get(u, v)];
    }
};

LCA lca;

int countChild(int u, int p) {
    child[u] = 1;
    for (auto e : adj[u]) {
        int v = e.F;
        if (v == p || del[v]) continue;
        child[u] += countChild(v, u);
    }
    return child[u];
}

int centroid(int u, int p, int m) {
    for (auto e : adj[u]) {
        int v = e.F;
        if (v == p || del[v]) continue;
        if (child[v] > m / 2) return centroid(v, u, m);
    }
    return u;
}

int cd(int u = 1) {
    int m = countChild(u, 0);
    u = centroid(u, 0, m);
    del[u] = 1;
    for (auto e : adj[u]) {
        int v = e.F;
        if (del[v]) continue;
        int x = cd(v);
        par[x] = u;
        cenAdj[x].push_back(u);
        cenAdj[u].push_back(x);
    }
    return u;
}

vector<int> subtree[N];

void calcDist(int u, int p) {
    subtree[u].push_back(u);
    distVals[u].push_back(0);
    if (p != -1) parDist[u].push_back(lca.Dist(p, u));
    for (int v : cenAdj[u]) {
        if (v == p) continue;
        calcDist(v, u);
        for (auto c : subtree[v]) {
            subtree[u].push_back(c);
            distVals[u].push_back(lca.Dist(u, c));
            if (p != -1)
                parDist[u].push_back(lca.Dist(p, c));
        }
    }
    sort(all(distVals[u]));
    sort(all(parDist[u]));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")) {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w" , stdout);
    }

    int numNode, numQuery;
    cin >> numNode >> numQuery;
    FOR(i, 1, numNode - 1) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    lca.setupLCA(numNode);
    int root = cd();
    par[root] = root;

    calcDist(root, -1);

    while (numQuery--) {
        int u;
        ll l;
        cin >> u >> l;
        int ans = upper_bound(all(distVals[u]), l) - distVals[u].begin();
        int p = u;
        while (true) {
            if (par[p] == p) break;
            ll d = l - lca.Dist(u, par[p]);
            ans += upper_bound(all(distVals[par[p]]), d) - distVals[par[p]].begin();
            ans -= upper_bound(all(parDist[p]), d) - parDist[p].begin();
            p = par[p];
        }
        cout << ans << "\n";
    }

    return 0;
}


Leave a Comment