#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];
int cnt = 1,N,Left,Right,Val,T;
void dfs(int x){
l[x] = cnt++;
for(auto s: adj[x]){
if(s.first != p[x]){
p[s.first] = x;
v[s.first] = v[x] + s.second;
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;
}
signed main(){
int n,q; cin >> n >> q;
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});
}
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;
for(int i = 0; i < q; i++){
int t; cin >> t;
if(t == 1){
int s; cin >> s;
if(seg[1][1]){
cout << seg[1][0] << endl;
}else{
cout << -1 << endl;
}
}else if(t == 2){
int vv; cin >> vv;
grape[vv] = !grape[vv];
T = grape[vv];
Left = l[vv]; Right = l[vv];
Update();
}else{
int a,b,c; cin >> a >> b >> c;
for(int j = 0; j < adj[a].size(); j++){
if(adj[a][j].first == b) Val = c - adj[a][j].second;
}
if(p[a] == b) {Left = l[a]; Right = r[a];}
else {Left = l[b]; Right = r[b];}
T = -1;
Update();
for(int j = 0; j < adj[a].size(); j++){
if(adj[a][j].first == b) adj[a][j].second = c;
}
for(int j = 0; j < adj[b].size(); j++){
if(adj[b][j].first == a) adj[b][j].second = c;
}
}
}
}
/*
2 4
1 1
4
3 1 3 2
1 1
2
2 3
3 2 1 2
2 4
1 1
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:167:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for(int j = 0; j < adj[a].size(); j++){
| ~~^~~~~~~~~~~~~~~
Main.cpp:174:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for(int j = 0; j < adj[a].size(); j++){
| ~~^~~~~~~~~~~~~~~
Main.cpp:177:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int j = 0; j < adj[b].size(); j++){
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
256 ms |
20424 KB |
Output is correct |
| 2 |
Correct |
265 ms |
21252 KB |
Output is correct |
| 3 |
Correct |
316 ms |
21184 KB |
Output is correct |
| 4 |
Correct |
267 ms |
23008 KB |
Output is correct |
| 5 |
Correct |
251 ms |
21728 KB |
Output is correct |
| 6 |
Correct |
252 ms |
22124 KB |
Output is correct |
| 7 |
Execution timed out |
3060 ms |
21088 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
230 ms |
20856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
209 ms |
20152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
253 ms |
19924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
