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

trick1:

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

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

trick2:

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

∑i∈S1∑j∈S2aiaj\sum_{i\in S_1}\sum_{j\in S_2}a_ia_j

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

(∑i∈S1ai)(∑i∈S2ai)(\sum_{i\in S_1}a_i) (\sum_{i\in S_2}a_i)

结合上面两个 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;
}

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

2 条评论

  • @ 2026-5-23 9:39:56

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

    👍 1
    • @ 2026-5-23 9:39:39

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

      • 1
      13
      已通过
      0
      题解被赞
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. 兼容模式
      8. 主题
      3. Worker 0, 14ms
      4. Powered by Hydro v4.12.2 Community