萌新刚学 OI，求助线段树合并

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5, L = 18;
mt19937 rnd(time(nullptr));
ll Abs(ll x) {
	return ((x < 0) ? (-x) : (x));
}
ll hsh[N + 10];
struct node {
	int to; ll val;
	node(int T, ll V) {
		to = T, val = V;
	}
};
vector <node> tgra[N + 10];
struct dot {
	int ind; ll dis;
	bool operator < (const dot &other) const {
		return dis < other.dis;
	}
};
vector <dot> anc[N + 10]; vector <int> mpi[N + 10];
vector <dot> sub[N + 10];
int n, siz[N + 10], maxpart = N, remain = N, root = 0;
ll dr[N + 10];
bool vis[N * L + 10];
void getsiz(int u, int fa) {
	siz[u] = 1;
	for(int i = 0; i < tgra[u].size(); i++) {
		int v = tgra[u][i].to;
		if(v == fa || vis[v]) continue;
		getsiz(v, u);
		siz[u] += siz[v];
	}
} 
void getrt(int u, int fa) {
	int rest = 0;
	for(int i = 0; i < tgra[u].size(); i++) {
		int v = tgra[u][i].to;
		if(v == fa || vis[v]) continue;
		rest = max(rest, siz[v]);
		getrt(v, u);
	}
	rest = max(rest, remain - siz[u]);
	if(rest < maxpart) {
		maxpart = rest;
		root = u;
	}
}
void trav(int u, int fa, ll dist, int a) {
	anc[u].push_back((dot){a, dist});
	sub[a].push_back((dot){u, dist});
	for(int i = 0; i < tgra[u].size(); i++) {
		int v = tgra[u][i].to;
		if(v == fa || vis[v]) continue;
		trav(v, u, dist + tgra[u][i].val, a);
	}
}
void work(int u) {
	anc[u].push_back((dot){u, 0ll});
	sub[u].push_back((dot){u, 0ll});
	for(int i = 0; i < tgra[u].size(); i++) {
		int v = tgra[u][i].to;
		if(vis[v]) continue;
		trav(v, u, tgra[u][i].val, u);
	}
	vis[u] = 1;

	for(int i = 0; i < tgra[u].size(); i++) {
		int v = tgra[u][i].to;
		if(vis[v]) continue;
		getsiz(v, u);
		remain = siz[v], maxpart = N, root = 0;
		getrt(v, u);
		work(root);
	}
}

int limit = 0;
vector <int> gra[N * L + 10], ngr[N * L + 10];
void link(int x, int y) {
	// cout << x << ' ' << y << '\n';
	gra[x].push_back(y);
	ngr[y].push_back(x);
}
int que[N * L + 10], tot = 0, col[N * L + 10], cl = 0, alltot = 0;
int cntval[N * L + 10], hshval[N * L + 10];
void dfs1(int u) {
	vis[u] = 1;
	for(int i = 0; i < ngr[u].size(); i++) {
		int v = ngr[u][i];
		if(vis[v]) continue;
		dfs1(v);
	}
	que[++tot] = u;
}
void dfs2(int u) {
	col[u] = cl;
	if(u <= n)
		cntval[cl]++, hshval[cl] ^= hsh[u];
	for(int i = 0; i < gra[u].size(); i++) {
		int v = gra[u][i];
		if(col[v]) continue;
		dfs2(v);
	}
}
void kj() {
	for(int i = 1; i <= alltot; i++) vis[i] = 0;
	for(int i = 1; i <= alltot; i++)
		if(!vis[i]) dfs1(i);
	for(int i = alltot; i >= 1; i--) {
		int u = que[i];
		if(!col[u]) {
			cl++;
			dfs2(u);
		}
	}
	// cout << "T1" << endl;
	for(int i = 1; i <= alltot; i++) ngr[i].clear();
	for(int i = 1; i <= alltot; i++) {
		for(int j = 0; j < gra[i].size(); j++) {
			int u = col[i], v = col[gra[i][j]];
			if(u != v) {
				ngr[v].push_back(u);
			}
		}
	}
	// cout << "T2" << endl;
	// cout << cl << endl;
}

int ans[N * L + 10];
struct info {
	int ls, rs;
	int cnt; int sum;
} T[N * 900 + 10];
void push_up(int now) {
	T[now].cnt = T[T[now].ls].cnt + T[T[now].rs].cnt;
	T[now].sum = (T[T[now].ls].sum ^ T[T[now].rs].sum);
}
int rt[N * L + 10], ttot = 0, lstcnt = 0;
int upd(int pos, int s, int t, int now, int cntval, int hshval) {
	if(!now) now = ++ttot;
	if(s == t) {
		T[now].cnt += cntval;
		T[now].sum += hshval;
		return now;
	}
	int mid = (s + t) >> 1;
	if(pos <= mid) T[now].ls = upd(pos, s, mid, T[now].ls, cntval, hshval);
	else T[now].rs = upd(pos, mid + 1, t, T[now].rs, cntval, hshval);
	push_up(now);
	return now;
}
int qry(int pos, int s, int t, int now) {
	if(s == t) {
		return T[now].cnt;
	}
	int mid = (s + t) >> 1;
	if(pos <= mid) return qry(pos, s, mid, T[now].ls);
	else return qry(pos, mid + 1, t, T[now].rs);
}
int merge(int x, int y, int s, int t) {
	if(!x && !y) return 0;
	if(!x || !y) return x + y;
	if(T[x].cnt == T[y].cnt && T[x].sum == T[y].sum) return x;
	int mid = (s + t) >> 1, z = (x <= lstcnt ? ++ttot : x);
	T[z].ls = merge(T[x].ls, T[y].ls, s, mid);
	T[z].rs = merge(T[x].rs, T[y].rs, mid + 1, t);
	push_up(z);
	return z;
}
void topo() {
	for(int i = 1; i <= cl; i++)
		if(cntval[i]) limit++;
	int tmp = 0;
	for(int i = 1; i <= cl; i++)
		if(cntval[i])
			rt[i] = upd(++tmp, 1, limit, rt[i], cntval[i], hshval[i]);
	for(int u = 1; u <= cl; u++) {
		ans[u] = T[rt[u]].cnt;
		lstcnt = ttot;
		for(int i = 0; i < ngr[u].size(); i++) {
			int v = ngr[u][i];
			rt[v] = merge(rt[v], rt[u], 1, limit);
        }
	}
}
int main() {
	// freopen("read.in", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> dr[i], hsh[i] = Abs(rnd());
	for(int i = 1, x, y; i < n; i++) {
		ll z; cin >> x >> y >> z;
		tgra[x].push_back(node(y, z));
		tgra[y].push_back(node(x, z));
	}
	// cout << "Q1" << endl;
	remain = n, maxpart = n, root = 0;
	getsiz(1, 0), getrt(1, 0);
	work(root);
	// cout << "Q2" << endl;
	alltot = n;
	for(int i = 1; i <= n; i++) {
		sort(sub[i].begin(), sub[i].end());
		mpi[i].push_back(sub[i][0].ind);
		for(int j = 1; j < sub[i].size(); j++) {
			link(++alltot, sub[i][j].ind);
			link(alltot, mpi[i].back());
			mpi[i].push_back(alltot);
		}
	}
	// cout << "Q3" << endl;
	// cout << alltot << endl;

	for(int u = 1; u <= n; u++) {
		// cout << u << ':';
		for(int i = 0; i < anc[u].size(); i++) {
			int a = anc[u][i].ind;
			ll lim = dr[u] - anc[u][i].dis;

			int L = 0, R = (int)sub[a].size() - 1, pos = -1;
			while(L <= R) {
				int mid = (L + R) >> 1;
				if(sub[a][mid].dis <= lim) L = mid + 1, pos = mid;
				else R = mid - 1;
			}
			if(pos >= 0) {
				link(u, mpi[a][pos]);
			}
		}
	}
	// cout << "Q4" << endl;
	kj();
	// cout << "Q5" << endl;
	topo();

	for(int i = 1; i <= n; i++)
		cout << ans[col[i]] << ' ';
	// cerr << ttot << endl;
}