预言
2025-07-18 20:39:18
发布于：湖南
22阅读
0回复
0点赞
https://codeforces.com/contest/2126/submission/329515825
This submission will time limit exceeded on test 51.
code:
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <cmath>
#define int long long
using namespace std;
vector <pair <int, int>> v[200005];
vector <int> big;
int idx[200005];
map <int, int> cont[505];
vector <pair <int, int>> v2[200005];
int siz;
int a[200005];
void solve(){
int n, m;
cin >> n >> m;
siz = sqrt(n);
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);
cont[idx[j.first]][a[i]] -= j.second;
cont[idx[j.first]][0] += j.second;
}
}
}
//cout << ans << '\n';
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[idx[x]][0] + cont[idx[x]][a[x]]);
ans += (cont[idx[x]][0] + cont[idx[x]][y]);
}
for(auto i:v2[x]){
cont[idx[i.first]][a[x]] += i.second;
cont[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;
}
for(int i = 0; i < big.size(); i++){
cont[i].clear();
}
big.clear();
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度 。
注意到当 时，。
有帮助，赞一个