# Untitled

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

#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;
}

int child[N], par[N];
bool del[N];
vector<ll> distVals[N], parDist[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;
}
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);
}

int numNode, numQuery;
cin >> numNode >> numQuery;
FOR(i, 1, numNode - 1) {
int u, v, c;
cin >> u >> v >> 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;
}

```