那晚CF F..FT tlqtj jbl
2025-07-20 14:17:16
发布于：湖南
46阅读
0回复
0点赞
这道题我经过两天的激战后，我终于把它过了！
翻译：
给定一个 个节点的树，树上的第 个节点有一个颜色 ，编号为 的边连接 ，并且有一个值 。
定义第 条边的美丽值为：
如果这条边连接的节点颜色相同（即 ），美丽值为 ；否则美丽值为 。
有 次操作，每次操作会改变一个点的颜色，并且询问此时这棵树所有边的美丽值之和。
正难则反。我们预处理出所有 之和，然后减去所有连接的两个节点相同的边的 就是它的美丽值。
考虑根号分治。设置阈值为 ，当一个点的度数大于等于 ，则称这个点为度较多的点，否则为度较少的点。
我们可以用个哈希表 ， 表示当第 个度较多的点颜色为 时，对美丽值的减少产生的贡献。
在查询时，对于度较少的点，直接暴力统计；而对于度较多的点，直接查表即可。得出答案后别忘了更新表。
显然度较多的点不会超过 ，而每次查询暴力统计的点数不超过 ，故时间复杂度为 ，当 取 时，时间复杂度为 。
#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：
每次操作都选定最上面的节点，把每种颜色都选取一遍。显然，每次都会在 里面新增 个元素。此时的空间复杂度为 ，当 时为 ，已经超过 256MB 的限制了。
对此，我们可以进行这样的小优化：
哈希表 只记录度较少的点对度较多的点的贡献，度较多的点之间的贡献在询问时单独计算。由于度较少的点最多只与 个度较多的点相连（要是超过 了就变成度较多的点了），所以每次操作在 里面新增的元素不超过 个。空间复杂度就变为了 。
而且注意到本题时间限制较为宽松，故考虑调整 的大小，用时间换空间。我在这里设置的 。
#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;
}
有帮助，赞一个