///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
//#define int long long
const int N = 1e5 + 5, MAX = 1e6, MOD = 1e9 + 7;
const long long oo = 1e18;
int n, q, TIME, tidel;
int cnt[N], sz[N], del[N], nxt[N], h[N];
vector<pi> e[N];
vector<int> c[N];
vector<long long> m[N], lz[N], s[N];
pi ti[105][N];
map<int, int> W[N];
void down(int cen, int id){
if(lz[cen][id]){
s[cen][2 * id] += lz[cen][id];
if(m[cen][2 * id] < oo) m[cen][2 * id] += lz[cen][id];
lz[cen][2 * id] += lz[cen][id];
s[cen][2 * id + 1] += lz[cen][id];
if(m[cen][2 * id + 1] < oo) m[cen][2 * id + 1] += lz[cen][id];
lz[cen][2 * id + 1] += lz[cen][id];
lz[cen][id] = 0;
}
}
void update(int cen, int id, int l, int r, int u, int v, long long x){
if(l > v || r < u) return;
if(u <= l && r <= v){
s[cen][id] += x;
if(m[cen][id] < oo) m[cen][id] += x;
lz[cen][id] += x;
return;
}
down(cen, id);
int mid = (l + r) / 2;
update(cen, 2 * id, l, mid, u, v, x);
update(cen, 2 * id + 1, mid + 1, r, u, v, x);
m[cen][id] = min(m[cen][2 * id], m[cen][2 * id + 1]);
}
void update2(int cen, int id, int l, int r, int i){
if(i > r || i < l) return;
if(l == r){
c[cen][id] ^= 1;
m[cen][id] = (c[cen][id] ? s[cen][id] : oo);
// cout << s[cen][id] << "\n";
return;
}
down(cen, id);
int mid = (l + r) / 2;
update2(cen, 2 * id, l, mid, i);
update2(cen, 2 * id + 1, mid + 1, r, i);
m[cen][id] = min(m[cen][2 * id], m[cen][2 * id + 1]);
}
long long dis(int cen, int id, int l, int r, int u, int v){
if(l > v || r < u) return 0;
if(u <= l && r <= v){
return s[cen][id];
}
down(cen, id);
int mid = (l + r) / 2;
return dis(cen, 2 * id, l, mid, u, v) + dis(cen, 2 * id + 1, mid + 1, r, u, v);
}
void count_child(int u, int p){
cnt[u] = 1;
for(auto [v, w] : e[u]){
if(v != p && !del[v]){
count_child(v, u);
cnt[u] += cnt[v];
}
}
}
int find_centroid(int u, int p, int n){
for(auto [v, w] : e[u]){
if(v != p && !del[v] && cnt[v] > (n / 2)) return find_centroid(v, u, n);
}
return u;
}
void dfs(int u, int p, long long W, int cen){
ti[h[cen]][u].F = ++TIME;
update(cen, 1, 1, sz[cen], TIME, TIME, W);
for(auto [v, w] : e[u]){
if(v != p && !del[v]){
dfs(v, u, W + w, cen);
}
}
ti[h[cen]][u].S = TIME;
// ti[cen][u] = {in[u], out[u]};
}
void build(int u, int p){
count_child(u, p);
int cen = find_centroid(u, p, cnt[u]);
h[cen] = (p ? h[p] + 1 : 0);
nxt[cen] = p;
sz[cen] = cnt[u];
// cout << cen << " " << cnt[u] << "\n";
s[cen] = vector<long long> (4 * cnt[u], 0);
c[cen] = vector<int> (4 * cnt[u], 0);
m[cen] = vector<long long> (4 * cnt[u], oo);
lz[cen] = vector<long long> (4 * cnt[u], 0);
TIME = 0;
dfs(cen, p, 0, cen);
// cout << ti[cen][3].F << " " << dis(cen, 1, 1, sz[cen], ti[cen][3].F, ti[cen][3].F) << "\n";
del[cen] = ++tidel;
for(auto [v, w] : e[cen]){
if(!del[v]) build(v, cen);
}
}
void solve(){
cin >> n >> q;
FOR(i, 2, n){
int u, v, w; cin >> u >> v >> w;
if(u > v) swap(u, v);
e[u].pb({v, w});
e[v].pb({u, w});
W[u][v] = W[v][u] = w;
}
build(1, 0);
while(q--){
int t; cin >> t;
if(t == 1){
int s; cin >> s;
long long res = oo, u = s;
while(u != 0){
long long cost = dis(u, 1, 1, sz[u], ti[h[u]][s].F, ti[h[u]][s].F) + m[u][1];
res = min(res, cost);
u = nxt[u];
}
cout << (res > 1e14 ? -1 : res) << "\n";
}else if(t == 2){
int s; cin >> s;
int u = s;
while(u != 0){
update2(u, 1, 1, sz[u], ti[h[u]][s].F);
u = nxt[u];
}
}else{
int s, t, w; cin >> s >> t >> w;
if(del[s] > del[t]) swap(s, t);
int u = s;
while(u != 0){
if(ti[h[u]][s].F > ti[h[u]][t].F) swap(s, t);
update(u, 1, 1, sz[u], ti[h[u]][t].F, ti[h[u]][t].S, w - W[s][t]);
// cout << u << " " << s << " " << t << " " << w << " " << w - W[{s, t}] << " " << m[u][1] << "\n";
u = nxt[u];
}
if(s > t) swap(s, t);
W[s][t] = W[t][s] = w;
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inp("sown.inp");
// out("out.txt");
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:17:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:188:5: note: in expansion of macro 'inp'
188 | inp("sown.inp");
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |