#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 sub[200001];
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 Query2(int ll = 1, int rr = N, int ind = 1){
if(ll > Right or rr < Left) return 1e18;
if(ll != rr) Spread(ind);
if(ll >= Left and rr <= Right) {
if(seg[ind][1]) return seg[ind][0];
return 1e18;
}
int mid = (ll + rr) / 2;
return min(Query2(ll, mid, ind * 2), Query2(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});
}
for(int i = 1; i <= n; i++) sub[i] = 1e18;
dfs(1);
for(int i = 0; i < q; i++){
int t; cin >> t;
if(t == 1){
int s, ans = 1e18; cin >> s;
int dist = 0, x = s;
while(x != 1){
int y = x;
while(y != 1){
dist += d[{y/2,y}];
y/=2;
}
if(sub[x] != 1e18){
ans = min(ans, sub[x] + dist);
}
dist = 0;
x /= 2;
}
cout << ans << endl;
}else if(t == 2){
int vv; cin >> vv;
grape[vv] = !grape[vv];
if(grape[vv]){
sub[vv] = 0;
while(vv > 0){
sub[vv/2] = min(sub[vv/2],sub[vv] + d[{vv/2,vv}]);
vv/=2;
}
}else{
sub[vv] = 1e18;
if(vv * 2 <= n) sub[vv] = min(sub[vv * 2] + d[{vv,vv * 2}], sub[vv]);
if(vv * 2 + 1 <= n) sub[vv] = min(sub[vv * 2 + 1] + d[{vv, vv * 2 + 1}], sub[vv]);
while(vv > 0){
sub[vv/2] = min(sub[vv/2],sub[vv] + d[{vv/2,vv}]);
vv/=2;
}
}
}else{
int a,b,c; cin >> a >> b >> c;
Val = c - d[{min(a,b), max(a,b)}];
d[{min(a,b), max(a,b)}] = c;
int vv = min(a,b);
while(vv > 0){
sub[vv] = 1e8;
if(vv * 2 <= n) sub[vv] = min(sub[vv * 2] + d[{vv,vv * 2}], sub[vv]);
if(vv * 2 + 1 <= n) sub[vv] = min(sub[vv * 2 + 1] + d[{vv, vv * 2 + 1}], sub[vv]);
vv/=2;
}
}
}
}
/*
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 |
8 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
375 ms |
46772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
482 ms |
44860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
465 ms |
46788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
578 ms |
46636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
