那晚CF F..FT tlqtj jbl

cjdst

2025-07-20 14:17:16

发布于：湖南

45阅读

0回复

0点赞

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

翻译：

给定一个 $n$ 个节点的树，树上的第 $i$ 个节点有一个颜色 $A_i$ ，编号为 $i$ 的边连接 $X_i,Y_i$ ，并且有一个值 $C_i$ 。

定义第 $i$ 条边的美丽值为：

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

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

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

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

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

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

显然度较多的点不会超过 $\frac{n}{l}$ ，而每次查询暴力统计的点数不超过 $l$ ，故时间复杂度为 $O(ql+\frac{qn}{l})$ ，当 $l$ 取 $\sqrt{n}$ 时，时间复杂度为 $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：

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

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

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

而且注意到本题时间限制较为宽松，故考虑调整 $l$ 的大小，用时间换空间。我在这里设置的 $l=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;
}

通过记录

有帮助，赞一个

去预览

0/2000

全部评论 4

Eucatastrophe‌
为什么这题目这么喜欢美丽啊，美丽数都一大堆了咋又来个美丽树

2025-07-20 来自浙江
0
- cjdst
  回复
  Eucatastrophe‌
  其实原题目是求 cost，美丽值是我自己改的（（（
  
  2025-07-20 来自湖南
  0
- Eucatastrophe‌
  回复
  cjdst
  啊¿
  
  2025-07-20 来自浙江
  0
- Eucatastrophe‌
  回复
  cjdst
  但是美丽数确实一大堆
  
  2025-07-20 来自浙江
  0
Grapher
主播快去写昨晚ABC DE

2025-07-20 来自浙江
0
- cjdst
  回复
  Grapher
  我都没做
  
  2025-07-20 来自湖南
  0
- Grapher
  回复
  cjdst
  所以让你快去做
  
  2025-07-20 来自浙江
  0
- cjdst
  回复
  Grapher
  不做
  
  2025-07-20 来自湖南
  0
XRiaB
ddd

2025-07-20 来自广东
0
cjdst
ddd

2025-07-20 来自湖南
0

全部评论 4

热门讨论