那晚CF F..FT tlqtj jbl

userId_undefined

复仇者_帅童

小有名气CSP-J一等奖出题人

2025-07-20 14:17:16

发布于：湖南

42阅读
0回复
0点赞

这道题我经过两天的激战后，我终于把它过了！

翻译：

给定一个 nn 个节点的树，树上的第 ii 个节点有一个颜色 AiA_i，编号为 ii 的边连接 Xi,YiX_i,Y_i，并且有一个值 CiC_i。

定义第 ii 条边的美丽值为：

如果这条边连接的节点颜色相同（即 AXi=AYiA_{X_i}=A_{Y_i}），美丽值为 00；否则美丽值为 CiC_i。

有 QQ 次操作，每次操作会改变一个点的颜色，并且询问此时这棵树所有边的美丽值之和。

正难则反。我们预处理出所有 CiC_i 之和，然后减去所有连接的两个节点相同的边的 CiC_i 就是它的美丽值。

考虑根号分治。设置阈值为 ll，当一个点的度数大于等于 ll，则称这个点为度较多的点，否则为度较少的点。

我们可以用个哈希表 cont\tt{cont}，cont[i][j]\mathtt{cont}[i][j] 表示当第 ii 个度较多的点颜色为 jj 时，对美丽值的减少产生的贡献。

在查询时，对于度较少的点，直接暴力统计；而对于度较多的点，直接查表即可。得出答案后别忘了更新表。

显然度较多的点不会超过 nl\frac{n}{l}，而每次查询暴力统计的点数不超过 ll，故时间复杂度为 O(ql+qnl)O(ql+\frac{qn}{l})，当 ll 取 n\sqrt{n} 时，时间复杂度为 O(qn)O(q\sqrt n)。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <iostream>
#include <random>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#define int long long

using namespace __gnu_pbds;
using namespace std;

mt19937 rng;
unsigned s1, s2, s3;

int a[200005]; 
vector <pair <int, int>> v[200005];

int siz;
vector <int> big;//记录度较多的点
int idx[200005];
vector <pair <int, int>> v2[200005];
gp_hash_table <unsigned int, int> cont;

unsigned int get_hash(int x, int y){//获取哈希值，减少被卡概率
	unsigned int cur = x * 200005 + y;
	cur += s1;
	cur = (cur ^ (x >> 33)) * s2;
	cur = (cur ^ (x >> 30)) * s3;
	return cur;
}

void solve(){
	int n, m;
	cin >> n >> m;
	siz = sqrt(n);//阈值设置为 sqrtn
	for(int i = 1; i <= n; i++) cin >> a[i];
	int ans = 0;
	
	for(int i = 1; i < n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
		if(a[x] != a[y]) ans += z;//预处理出所有 C_i 的和
	}
	
	for(int i = 1; i <= n; i++){
		if(v[i].size() >= siz){//记录度较多的点
			big.push_back(i), idx[i] = big.size() - 1;
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(auto j:v[i]){
			if(v[j.first].size() >= siz){
				v2[i].push_back(j);
				cont[get_hash(idx[j.first], a[i])] += j.second;//预处理出贡献
			}
		}
	}
	
	while(m--){
		int x, y;
		cin >> x >> y;
		if(v[x].size() < siz){//度较少的点直接暴力计算
			for(auto i:v[x]){
				if(a[i.first] != a[x]) ans -= i.second;
				if(a[i.first] != y) ans += i.second;
			}
		}else{
			ans += cont[get_hash(idx[x], a[x])];//直接查表
			ans -= cont[get_hash(idx[x], y)];
		}
		for(auto i:v2[x]){
			cont[get_hash(idx[i.first], a[x])] -= i.second;//更新哈希表
			cont[get_hash(idx[i.first], y)] += i.second;
		}
		a[x] = y;
		cout << ans << '\n';
	}
	
	for(int i = 1; i <= n; i++){//记得清空
		v[i].clear();
		v2[i].clear();
		idx[i] = 0;
	}
	cont.clear();
	big.clear();
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	rng.seed(time(0));
	s1 = rng(), s2 = rng(), s3 = rng();
	int t;
	cin >> t;
	while(t--) solve();
	
	return 0;
}

大功告成……了吗？

交上去会发现 MLE on #37，原来可以构造这样一个hack：

每次操作都选定最上面的节点，把每种颜色都选取一遍。显然，每次都会在 cont\tt{cont} 里面新增 nl\frac{n}{l} 个元素。此时的空间复杂度为 O(n2l)O( \frac{n^2}{l})，当 l=nl=\sqrt n 时为 O(nn)O(n\sqrt n)，已经超过 256MB 的限制了。

对此，我们可以进行这样的小优化：

哈希表 cont\tt{cont} 只记录度较少的点对度较多的点的贡献，度较多的点之间的贡献在询问时单独计算。由于度较少的点最多只与 ll 个度较多的点相连（要是超过 ll 了就变成度较多的点了），所以每次操作在 cont\tt{cont} 里面新增的元素不超过 ll 个。空间复杂度就变为了 O(min⁡{n2l,ql})O(\min\{\frac{n^2}{l},ql\})。

而且注意到本题时间限制较为宽松，故考虑调整 ll 的大小，用时间换空间。我在这里设置的 l=200l=200。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <iostream>
#include <random>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#define int long long

using namespace __gnu_pbds;
using namespace std;

mt19937 rng;
unsigned s1, s2, s3;

int a[200005]; 
vector <pair <int, int>> v[200005];

int siz;
vector <int> big;//记录度较多的点
int idx[200005];
vector <pair <int, int>> v2[200005];
gp_hash_table <unsigned int, int> cont_small;

unsigned int get_hash(int x, int y){//获取哈希值，减少被卡概率
	unsigned int cur = x * 200005 + y;
	cur += s1;
	cur = (cur ^ (cur >> 33)) * s2;
	cur = (cur ^ (cur >> 30)) * s3;
	return cur;
}

int count_cont(int idx, int val){//度较多的点之间单独计算
	int ans = 0;
	for(auto i:v2[idx]){
		if(a[i.first] == val) ans += i.second;
	}
	return ans;
}

void solve(){
	int n, m;
	cin >> n >> m;
	siz = 200;//阈值调成200，节省内存
	for(int i = 1; i <= n; i++) cin >> a[i];
	int ans = 0;
	
	for(int i = 1; i < n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
		if(a[x] != a[y]) ans += z;
	}
	
	for(int i = 1; i <= n; i++){
		if(v[i].size() >= siz){
			big.push_back(i), idx[i] = big.size() - 1;
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(auto j:v[i]){
			if(v[j.first].size() >= siz){
				v2[i].push_back(j);
				if(v[i].size() < siz) cont_small[get_hash(idx[j.first], a[i])] += j.second;//度较少的点与度较多的点之间的边的贡献
			}
		}
	}
	
	while(m--){
		int x, y;
		cin >> x >> y;
		if(v[x].size() < siz){
			for(auto i:v[x]){//暴力算
				if(a[i.first] != a[x]) ans -= i.second;
				if(a[i.first] != y) ans += i.second;
			}
			for(auto i:v2[x]){//更新哈希表
				cont_small[get_hash(idx[i.first], a[x])] -= i.second;
				cont_small[get_hash(idx[i.first], y)] += i.second;
			}
		}else{
			ans += cont_small[get_hash(idx[x], a[x])] + count_cont(x, a[x]);//查表+单独计算
			ans -= cont_small[get_hash(idx[x], y)] + count_cont(x, y);
		}
		a[x] = y;
		cout << ans << '\n';
	}
	
	for(int i = 1; i <= n; i++){//记得清空
		v[i].clear();
		v2[i].clear();
		idx[i] = 0;
	}
	cont_small.clear();
	big.clear();
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	rng.seed(time(0));
	s1 = rng(), s2 = rng(), s3 = rng();
	int t;
	cin >> t;
	while(t--) solve();
	
	return 0;
}

通过记录

userId_undefined
去预览
0/2000

全部评论 4

热门讨论