这题是两个经典 trick 的缝合产物。

trick1:

如果将每个节点用 dfs 序编号，那么一颗子树内所有节点的编号是连续的一段区间。

因为用 dfs 访问到一个节点后，是先向下继续访问它的子节点然后再回溯到父节点遍历其他节点。所以一颗子树访问的次序序一定是连续的一段区间。

trick2:

设要求的两颗子树的节点集合分别为 $S_1,S_2$，那么题目要求的就是这么个式子：

这个东西可以把两个 sigma 拆开，得到：

结合上面两个 trick，这道题就被转变成了区间加区间求和的问题了。然后就可以直接线段树了。当然也可以二维树状数组，常数貌似比线段树小挺多，理解了之后码量也比线段树小很多，比较好写好调。但是这玩意的原理有亿点复杂，谨慎学习。

code：（线段树）

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define lowbit(x) (x & -x)
#define fo(i,j,k,l) for(int i = j;i <= k;i += l)
using namespace std;
const int mod = 1145141919;
int n,q;
int a[100005];
int t[1000005],tag[1000005];
vector<int>nxt[100005];
int dfn[100005],cnt,p[100005];
int ls[100005],rs[100005];
void dfs(int x) {
	dfn[x] = ++ cnt;
	p[dfn[x]] = x;
	ls[x] = cnt;
	fo(i,0,nxt[x].size() - 1,1) {
		if(dfn[nxt[x][i]])continue;
		dfs(nxt[x][i]);
	}
	rs[x] = cnt;
}
void build(int x,int l,int r) {
	if(l == r) {
		t[x] = a[p[l]] % mod;
		return; 
	}
	int mid = (l + r) >> 1;
	build(x << 1,l,mid);
	build((x << 1) | 1,mid + 1,r);
	t[x] = (t[x << 1] + t[(x << 1) | 1]) % mod;
}
void pushdown(int x,int l,int r) {
	if(l == r) {
		tag[x] = 0;
		return;
	}
	int mid = (l + r) >> 1;
	t[x << 1] += (tag[x] * (mid - l + 1)) % mod;
	t[x << 1] %= mod;
	tag[x << 1] += tag[x];
	tag[x << 1] %= mod;
	t[(x << 1) | 1] += (tag[x] * (r - (mid + 1) + 1)) % mod;
	t[(x << 1) | 1] % mod;
	tag[(x << 1) | 1] += tag[x];
	tag[(x << 1) | 1] %= mod;
	tag[x] = 0;
}
void update(int x,int l,int r,int L,int R,int k) {
	if(L <= l && r <= R) {
		t[x] += (k * (r - l + 1)) % mod;
		t[x] %= mod;
		tag[x] += k;
		tag[x] %= mod;
		return;
	}
	pushdown(x,l,r);
	int mid = (l + r) >> 1;
	if(l <= R && mid >= L)update(x << 1,l,mid,L,R,k);
	if(mid + 1 <= R && r >= L)update((x << 1) | 1,mid + 1,r,L,R,k);
	t[x] = (t[x << 1] + t[(x << 1) | 1]) % mod;
}
int query(int x,int l,int r,int L,int R) {
	if(L <= l && r <= R) {
		return t[x];
	}
	pushdown(x,l,r);
	int mid = (l + r) >> 1;
	int res = 0;
	if(l <= R && mid >= L)res += query(x << 1,l,mid,L,R);
	if(mid + 1 <= R && r >= L)res += query((x << 1) | 1,mid + 1,r,L,R);
	return res % mod;
}
signed main()
{
	freopen("worldtree.in","r",stdin);
	freopen("worldtree.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	fo(i,1,n,1) {
		cin >> a[i];
	}
	fo(i,1,n - 1,1) {
		int u,v;
		cin >> u >> v;
		nxt[u].push_back(v);
		nxt[v].push_back(u);
	}
	dfs(1);
	build(1,1,n);
	while(q --) {
		int op;
		cin >> op;
		if(op == 1) {
			int x,k;
			cin >> x >> k;
			update(1,1,n,ls[x],rs[x],k);
		}
		else {
			int x,y;
			cin >> x >> y;
			int ans1 = query(1,1,n,ls[x],rs[x]);
			int ans2 = query(1,1,n,ls[y],rs[y]);
			cout << (ans1 * ans2) % mod << endl;
		}
	}
	return 0;
}

为啥都喜欢用结构体封装？