#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e5 + 1;
const string NAME = "";
int n, q;
vector<ii> adj[N];
int lg[2 * N], euler[19][2 * N], tin[N], tout[N], EulerTourTraversal;
void DFS_EulerTour(int u = 1, int p = 0){
tin[u] = ++EulerTourTraversal;
euler[0][EulerTourTraversal] = u;
for(auto [v, w] : adj[u]){
if(v == p)
continue;
DFS_EulerTour(v, u);
euler[0][++EulerTourTraversal] = u;
}
tout[u] = EulerTourTraversal;
}
int min_by_time(int u, int v){
return tin[u] < tin[v] ? u : v;
}
int LCA(int u, int v){
int l = min(tin[u], tin[v]), r = max(tout[u], tout[v]);
int k = lg[r - l + 1];
return min_by_time(euler[k][l], euler[k][r - (1 << k) + 1]);
}
void initEulerTour(){
DFS_EulerTour();
for(int i = 2; i <= EulerTourTraversal; ++i)
lg[i] = lg[i / 2] + 1;
for(int l = 1; l <= lg[EulerTourTraversal]; ++l)
for(int i = 1; i <= EulerTourTraversal - (1 << l) + 1; ++i)
euler[l][i] = min_by_time(euler[l - 1][i], euler[l - 1][i + (1 << (l - 1))]);
}
const long long inf = 1e16;
struct SegmentTree{
int n, h;
vector<long long> tree, lazy;
SegmentTree(int _n = 0) : n(_n){
tree.resize(2 * n, 0);
lazy.resize(n, 0);
h = sizeof(int) * 8 - __builtin_clz(n);
}
void up(int u){
while(u > 1)
u >>= 1, tree[u] = min(tree[u << 1], tree[u << 1 | 1]) + lazy[u];
}
void apply(int u, long long val){
tree[u] += val;
if(u < n)
lazy[u] += val;
}
void down(int u){
for(int s = h; s; --s){
int i = u >> s;
if(lazy[i]){
apply(i << 1, lazy[i]);
apply(i << 1 | 1, lazy[i]);
lazy[i] = 0;
}
}
}
void update(int l, int r, long long val){
--l;
l += n, r += n;
int l0 = l, r0 = r;
for(; l < r; l >>= 1, r >>= 1){
if(l & 1)
apply(l++, val);
if(r & 1)
apply(--r, val);
}
up(l0);
up(r0 - 1);
}
long long get(int l, int r){
--l;
l += n, r += n;
down(l);
down(r - 1);
long long res = 2LL * inf;
for(; l < r; l >>= 1, r >>= 1){
if(l & 1)
res = min(res, tree[l++]);
if(r & 1)
res = min(tree[--r], res);
}
return res;
}
};
SegmentTree d;
int L[N], R[N], unused_variables_number_1;
long long W[N];
void DFS_TraversalOrder(int u = 1, int p = 0){
L[u] = ++unused_variables_number_1;
for(auto [v, w] : adj[u]){
if(v == p)
continue;
W[v] = w;
DFS_TraversalOrder(v, u);
}
R[u] = unused_variables_number_1;
}
long long dist(int u, int v){
int lca_uv = LCA(u, v);
return d.get(L[u], L[u]) + d.get(L[v], L[v]) - 2LL * d.get(L[lca_uv], L[lca_uv]);
}
int CurrentGrapes;
bool GrapeTree[N];
SegmentTree Node[N];
int sz[N];
bool del[N];
vector<int> g[N];
stack<int> stk;
int CentroidRoot;
int CenPar[N], depthCentroid[N];
void DFS_centroid(int u, int p = 0){
sz[u] = 1;
for(auto [v, w] : adj[u]){
if(v == p || del[v])
continue;
DFS_centroid(v, u);
sz[u] += sz[v];
}
}
int centroid(int u, int p, int n){
for(auto [v, w] : adj[u]){
if(v == p || del[v])
continue;
if(sz[v] > n / 2)
return centroid(v, u, n);
}
return u;
}
void decom(int u = 1){
DFS_centroid(u);
int root = centroid(u, 0, sz[u]);
if(stk.empty())
CentroidRoot = root;
if(!stk.empty())
g[stk.top()].pb(root), CenPar[root] = stk.top();
stk.push(root);
del[root] = true;
for(auto [v, w] : adj[root])
if(!del[v])
decom(v);
stk.pop();
}
void createChildID(int u){
int m = g[u].size();
for(int i = 0; i < m; ++i){
int v = g[u][i];
depthCentroid[v] = depthCentroid[u] + 1;
createChildID(v);
for(int zz : g[v])
g[u].pb(zz);
}
g[u].pb(u);
sort(g[u].begin(), g[u].end());
g[u].resize(unique(g[u].begin(), g[u].end()) - g[u].begin());
m = g[u].size();
Node[u] = SegmentTree(m);
for(int i = 0; i < m; ++i)
Node[u].update(i + 1, i + 1, dist(u, g[u][i]) + inf);
}
void inp(){
cin >> n >> q;
for(int i = 1; i < n; ++i){
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
}
void solve(){
d = SegmentTree(n);
initEulerTour();
DFS_TraversalOrder();
for(int i = 1; i <= n; ++i)
d.update(L[i], R[i], W[i]);
decom();
createChildID(CentroidRoot);
while(q--){
int type;
cin >> type;
if(type == 1){
int u;
cin >> u;
if(!CurrentGrapes){
cout << "-1\n";
continue;
}
int v = u;
long long ans = inf;
while(v != 0){
ans = min(ans, Node[v].get(1, g[v].size()) + dist(u, v));
v = CenPar[v];
}
cout << ans << "\n";
}
else if(type == 2){
int u;
cin >> u;
if(GrapeTree[u]){
--CurrentGrapes;
GrapeTree[u] = false;
int v = u;
while(v != 0){
int idx = lower_bound(g[v].begin(), g[v].end(), u) - g[v].begin() + 1;
Node[v].update(idx, idx, inf);
v = CenPar[v];
}
}
else{
++CurrentGrapes;
GrapeTree[u] = true;
int v = u;
while(v != 0){
int idx = lower_bound(g[v].begin(), g[v].end(), u) - g[v].begin() + 1;
Node[v].update(idx, idx, -inf);
v = CenPar[v];
}
}
}
else{
int u, v, w;
cin >> u >> v >> w;
int z = u + v - LCA(u, v);
if(depthCentroid[u] > depthCentroid[v])
swap(u, v);
int vv = v;
while(vv != CenPar[u]){
int idx = lower_bound(g[vv].begin(), g[vv].end(), v) - g[vv].begin() + 1;
Node[vv].update(idx, idx, -dist(v, vv));
vv = CenPar[vv];
}
d.update(L[z], R[z], -W[z]);
W[z] = w;
d.update(L[z], R[z], W[z]);
vv = v;
while(vv != CenPar[u]){
int idx = lower_bound(g[vv].begin(), g[vv].end(), v) - g[vv].begin() + 1;
Node[vv].update(idx, idx, dist(vv, v));
vv = CenPar[vv];
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen((NAME + ".inp").c_str(), "r")){
freopen((NAME + ".inp").c_str(), "r", stdin);
freopen((NAME + ".out").c_str(), "w", stdout);
}
inp();
solve();
}
/*
7 11
1 2 2
2 3 4
5 6 1
5 3 6
3 7 6
2 4 9
2 6
2 4
2 7
1 1
3 2 3 0
1 1
3 6 5 0
1 1
3 3 5 0 3 2 4 0
1 1
*/
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:330:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
330 | freopen((NAME + ".inp").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:331:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
331 | freopen((NAME + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |