#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#define endl '\n'
#define int long long
#define mod 1000000007
using namespace std;
vector<pair<int,int>>adj[200001];
int grape[200001], p[200001],seg[1000001][2],v[200001],l[200001],r[200001],lazy[1000001], depth[200001];
int cnt = 1,N,Left,Right,Val,T;
int sparse[200001][30];
void dfs(int x){
depth[x]++;
sparse[x][0] = p[x];
for(int j = 1; (1 << j) <= depth[x]; j++) sparse[x][j] = sparse[sparse[x][j - 1]][j - 1];
l[x] = cnt++;
for(auto s: adj[x]){
if(s.first != p[x]){
p[s.first] = x;
v[s.first] = v[x] + s.second;
depth[s.first] += depth[x];
dfs(s.first);
}
}
r[x] = cnt - 1;
}
void Spread(int ind){
if(lazy[ind] != 0){
seg[ind * 2][0] += lazy[ind];
seg[ind * 2 + 1][0] += lazy[ind];
lazy[ind * 2] += lazy[ind];
lazy[ind * 2 + 1]+= lazy[ind];
}
lazy[ind] = 0;
}
void Update(int ll = 1, int rr = N, int ind = 1){
if(ll > Right or rr < Left) return;
if(ll != rr) Spread(ind);
if(ll >= Left and rr <= Right){
if(T == 0) seg[ind][1] = 0;
else if(T == 1) seg[ind][1] = 1;
else{
seg[ind][0] += Val;
lazy[ind] += Val;
}
return;
}
int mid = (ll + rr) / 2;
Update(ll, mid, ind * 2);
Update(mid + 1, rr, ind * 2 + 1);
int v1 = 1e18, v2 = 1e18;
if(seg[ind * 2][1]) v1 = seg[ind * 2][0];
if(seg[ind * 2 + 1][1]) v2 = seg[ind * 2 + 1][0];
seg[ind][0] = min(v1,v2);
if(seg[ind][0] != 1e18) seg[ind][1] = 1;
else seg[ind][1] = 0;
}
int Query(int ll = 1, int rr = N, int ind = 1){
if(ll > Right or rr < Left) return 0;
if(ll != rr) Spread(ind);
if(ll >= Left and rr <= Right) return seg[ind][0];
int mid = (ll + rr) / 2;
return Query(ll, mid, ind * 2) + Query(mid + 1, rr, ind * 2 + 1);
}
int lca(int a, int b){
if(depth[a] > depth[b]) swap(a,b);
int diff = depth[b] - depth[a];
for(int j = 0; j < 30; j++){
if(diff & (1 << j)){
b = sparse[b][j];
}
}
for(int j = 29; j >= 0; j--){
if(sparse[a][j] != sparse[b][j]){
a = sparse[a][j];
b = sparse[b][j];
}
}
if(a != b) return sparse[a][0];
return a;
}
signed main(){
int n,q; cin >> n >> q;
map<pair<int,int>,int>d;
for(int i = 0; i < n - 1; i++){
int a,b,c; cin >> a >> b >> c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
d[{min(a,b), max(a,b)}] = c;
}
dfs(1);
N = exp2(ceil(log2(n)));
for(int i = 1; i <= n; i++) seg[l[i] + N - 1][0] = v[i];
for(int i = N - 1; i > 0; i--) seg[i][0] = 1e18;
int curr = 0;
for(int i = 0; i < q; i++){
int t; cin >> t;
if(t == 1){
int s; cin >> s;
int nw = lca(s, curr), ans = 0;
if(curr == 0){
cout << -1 << endl;
continue;
}
Left = l[s]; Right = l[s];
ans += Query();
Left = l[curr]; Right = l[curr];
ans += Query();
Left = l[nw]; Right = l[nw];
ans -= (2 * Query());
cout << ans << endl;
}else if(t == 2){
int vv; cin >> vv;
grape[vv] = !grape[vv];
if(grape[vv]) curr = vv;
else curr = 0;
T = grape[vv];
Left = l[vv]; Right = l[vv];
Update();
}else{
int a,b,c; cin >> a >> b >> c;
Val = c - d[{min(a,b), max(a,b)}];
if(p[a] == b) {Left = l[a]; Right = r[a];}
else {Left = l[b]; Right = r[b];}
T = -1;
Update();
d[{min(a,b), max(a,b)}] = c;
}
}
}
/*
2 4
1 1
4
3 1 3 2
1 1
2
2 3
3 2 1 2
2 4
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
50192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
259 ms |
49836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
329 ms |
49804 KB |
Output is correct |
| 2 |
Correct |
366 ms |
50700 KB |
Output is correct |
| 3 |
Correct |
350 ms |
51280 KB |
Output is correct |
| 4 |
Correct |
311 ms |
54168 KB |
Output is correct |
| 5 |
Correct |
328 ms |
52832 KB |
Output is correct |
| 6 |
Correct |
339 ms |
53744 KB |
Output is correct |
| 7 |
Correct |
243 ms |
50256 KB |
Output is correct |
| 8 |
Correct |
246 ms |
51380 KB |
Output is correct |
| 9 |
Correct |
261 ms |
50316 KB |
Output is correct |
| 10 |
Correct |
314 ms |
52836 KB |
Output is correct |
| 11 |
Correct |
321 ms |
51868 KB |
Output is correct |
| 12 |
Correct |
294 ms |
54692 KB |
Output is correct |
| 13 |
Correct |
228 ms |
50376 KB |
Output is correct |
| 14 |
Correct |
240 ms |
52316 KB |
Output is correct |
| 15 |
Correct |
249 ms |
50884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
367 ms |
49844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
