萌新刚学线段树合并，求助 36pts 的屑代码

#include <bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N = 1e5;
const ll Mod = 998244353;
int n, m;
struct tg {
	ll add, mul;
};
struct node {
	int ls, rs;
	tg tag;
} T[N * 300 + 10];
namespace sgt {
	int tot = 0, rt[N + 10];
	vector <int> bin;
	il int newnode(int add, int mul) {
		int now = 0;
		if(bin.size()) now = bin[bin.size() - 1], bin.pop_back();
		else now = ++tot;
//		now = ++tot; 
		T[now].ls = T[now].rs = 0;
		T[now].tag.add = add, T[now].tag.mul = mul;
		return now;
	}
	il void push_tag(int now, tg tag) {
		T[now].tag.add = (T[now].tag.add * tag.mul + tag.add) % Mod;
		T[now].tag.mul = T[now].tag.mul * tag.mul % Mod;
	}
	il void push_down(int now) {
		if(T[now].tag.add != 0 || T[now].tag.mul != 1) {
			if(!T[now].ls) T[now].ls = newnode(0, 0);
			if(!T[now].rs) T[now].rs = newnode(0, 0);
			push_tag(T[now].ls, T[now].tag);
			push_tag(T[now].rs, T[now].tag);
			T[now].tag.add = 0;
			T[now].tag.mul = 1;
		}
	}
	
	il void clear(int u) {
		bin.push_back(u);
		if(T[u].ls) clear(T[u].ls);
		if(T[u].rs) clear(T[u].rs);
	}
	il int upd(int ql, int qr, int s, int t, int now, tg tag) {
		if(ql <= s && t <= qr) {
			push_tag(now, tag);
			return now;
		}
		int mid = (s + t) >> 1;
		push_down(now);
		if(ql <= mid) T[now].ls = upd(ql, qr, s, mid, T[now].ls, tag);
		if(qr > mid) T[now].rs = upd(ql, qr, mid + 1, t, T[now].rs, tag);
		return now;
	}
	il ll qry(int pos, int s, int t, int now) {
		if(s == t) return T[now].tag.add;
		int mid = (s + t) >> 1;
		push_down(now);
		if(pos <= mid) return qry(pos, s, mid, T[now].ls);
		else return qry(pos, mid + 1, t, T[now].rs);
	}
	il int merge(int l, int r, int x, int y) {
		if(!x || !y) return x + y;
		if(l == r) {
			push_tag(x, (tg){0, T[y].tag.add});
			return x;
		}
		int mid = (l + r) >> 1;
		push_down(x);
		push_down(y);
		T[x].ls = merge(l, mid, T[x].ls, T[y].ls);
		T[x].rs = merge(mid + 1, r, T[x].rs, T[y].rs);
		return x;
	}
}
vector <int> gra[N + 10];
int dep[N + 10], up[N + 10];
void predfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	for(int i = 0; i < gra[u].size(); i++) {
		int v = gra[u][i];
		if(v == fa) continue;
		predfs(v, u);
	}
}
void dp(int u, int fa) {
	up[u] = max(up[u], up[fa]);
	for(int i = 0; i < gra[u].size(); i++) {
		int v = gra[u][i];
		if(v == fa) continue;
		dp(v, u);
	}
	
//	if(gra[u].size() == 1) cout << up[u] << ' ' << dep[u] << endl;
	sgt::rt[u] = sgt::newnode(0, 0);
	sgt::upd(up[u], dep[u] - 1, 0, n, sgt::rt[u], (tg){1, 1});
	for(int i = 0; i < gra[u].size(); i++) {
		int v = gra[u][i];
		if(v == fa) continue;
		ll rest = sgt::qry(dep[u], 0, n, sgt::rt[v]);
//		cout << v << ' ' << rest << ":"; 
		sgt::upd(0, dep[u], 0, n, sgt::rt[v], (tg){rest, 1});
//		for(int j = 0; j <= n; j++)
//			cout << sgt::qry(j, 0, n, sgt::rt[v]) << ' ';
//		cout << endl;
		sgt::merge(0, n, sgt::rt[u], sgt::rt[v]);
		sgt::clear(sgt::rt[v]);
	}
	
//	if(u == 1) return ;
//	cout << u << ' ' << up[u] << ' ' << dep[u] << ":";
//	for(int i = 0; i <= n; i++)
//		cout << sgt::qry(i, 0, n, sgt::rt[u]) << ' ';
//	cout << endl;
//	ll rest = sgt::qry(dep[u] - 1, 0, n, sgt::rt[u]);
//	sgt::upd(0, dep[u], 0, n, sgt::rt[u], (tg){rest, 1});
	
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1, x, y; i < n; i++) {
		cin >> x >> y;
		gra[x].push_back(y);
		gra[y].push_back(x);
	}
	predfs(1, 0);
	
	cin >> m;
	for(int i = 1, x, y; i <= m; i++) {
		cin >> x >> y;
		up[y] = max(up[y], dep[x]);
	}
	
	dp(1, 0);
	cout << sgt::qry(0, 0, n, sgt::rt[1]) << endl;
}