题解 - 洛谷仓库

验题人题解。

考虑对于一个

x

，枚举它的祖先

y

并钦定

y=\operatorname{LCA*}(x,i)

，设

z

为

y

的儿子且满足

x

在

z

的子树内，那么

y

对

x

的贡献就是

y

子树内的所有点的

f(u+d_y)

减去

z

子树内的所有点的

f(v+d_y)

，由于

d_z=d_y+1

，可以改写成

f(v+d_z-1)

。

那我们相当于要对每个

y

，求出它子树内的

f(u+d_y)

之和、

f(u+d_y-1)

之和。这样再做一个根到结点的前缀和就能对于每个

x

做到

O(1)

求得

s_x

了。

容易发现计算

f(u+d_y)

和

f(u+d_y-1)

的做法应当是本质相同的，因此我们下面只讨论计算

f(u+d_y)

之和的做法。

看到这个贡献形式我们首先想到丢到 01-Trie 上面计算贡献。考虑在 dfs 的同时对每个点维护一个 Trie 作为子树内的贡献信息，合并时考虑类似于线段树合并地合并两棵 Trie。

枚举

d_y

显然没什么前途。但是我们注意到

d

的性质和 dfs 结构的相关性，考虑在

u

处插入

u+d_u

，而在

y

处需要的贡献是

u+d_y

，因此在从

u

向上爬的时候每次将 Trie 的信息做一次全局减

1

，就能在

y

处获得正确的贡献。注意为了支持全局减操作，我们使用低位到高位的 01-Trie。

计算

f(u+d_y-1)

的过程也是同理，只要在做全局减

1

的前后都统计一下答案就能分别获得结果。

这样就做完了，时间复杂度是

O(Tn\log n)

。

CPP

#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
using namespace std;
const int N = 2e5 + 7;
int tr[N*30][2],sum[N*30];
int num;
int rt[N];
int n,q,mod,r;
vector<int>a[N];
int b[30][2];
int s[N],pl[N],pr[N];
int d[N];
void add(int &x,int y){x += y; if(x>=mod) x -= mod;}
int tmp[30];
void ins(int val,int id){
	int p = id;
	memset(tmp,0,sizeof tmp);
	for(int i=0;i<=20;++i){
		int x = (val >> i) & 1;
		if(!tr[p][x]) tr[p][x] = ++num;
		tmp[i] = b[i][x];
		p = tr[p][x]; 
	}
	for(int i=19;i>=0;--i) tmp[i] = 1ll * tmp[i+1] * tmp[i] % mod;
	p = id;
	for(int i=0;i<=20;++i){
		int x = (val >> i) & 1;
		add(sum[p],tmp[i]);
		p = tr[p][x]; 
	}
}
int merge(int x,int y){
	if(!x) return y;
	if(!y) return x;
	add(sum[x],sum[y]);
	tr[x][0] = merge(tr[x][0],tr[y][0]);
	tr[x][1] = merge(tr[x][1],tr[y][1]);
	return x;
}
void del(int x,int i){
	swap(tr[x][0],tr[x][1]);
	if(tr[x][1]) del(tr[x][1],i+1);
	sum[x] = 1ll * sum[tr[x][0]] * b[i][0] % mod;
	add(sum[x],1ll * sum[tr[x][1]] * b[i][1] % mod);
}
void dfs(int x,int fa){
	d[x] = d[fa] + 1;
	if(!rt[x]) rt[x] = ++num;
	for(auto c:a[x]){
		if(c==fa) continue;
		dfs(c,x);
		rt[x] = merge(rt[x],rt[c]);
	}
	ins(x+d[x],rt[x]);
	pl[x] = sum[rt[x]];
	del(rt[x],0);
	pr[x] = sum[rt[x]];
}
void calc(int x,int fa){
	s[x] = s[fa];
	add(s[x],pl[x]);
	if(x!=r) add(s[x],mod-pr[x]);
	for(auto c:a[x]){
		if(c==fa) continue;
		calc(c,x);
	}
}
void solve(){
	memset(s,0,sizeof s);
	memset(tr,0,sizeof tr);
	memset(rt,0,sizeof rt);
	memset(d,0,sizeof d);
	memset(sum,0,sizeof sum);
	num = 0;
	dfs(r,0);
	calc(r,0);
	long long ans = 0;
	for(int i=1;i<=n;++i) ans ^= 1ll * i * s[i];
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<n;++i){
		int u,v;
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	cin>>q;
	while(q--){
		cin>>r>>mod;
		for(int i=0;i<=20;++i) cin>>b[i][0];
		for(int i=0;i<=20;++i) cin>>b[i][1];
		solve();
	}
	return 0;
}

题解

文章操作

相关推荐

评论

题解