fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define n nnathw
  5. #define fi first
  6. #define se second
  7. #define MAX 100100
  8. #define pb push_back
  9. #define inf 100000000
  10.  
  11. int n,q;
  12. vector<pair<int,int> > adj[MAX];
  13. int w[MAX], head[MAX], parent[MAX], treesize[MAX], depth[MAX], pos[MAX];
  14. int cnt = 0;
  15.  
  16. struct segtree
  17. {
  18.     vector<int> st1,st2;
  19.     int n;
  20.     vector<int> a;
  21.  
  22.     segtree(int _n, vector<int> &_a)
  23.     {
  24.         n = _n;
  25.         a.resize(n+1);
  26.         st1.resize(n*4+10, 0);
  27.         st2.resize(n*4+10,inf);
  28.         for(int i = 1; i<=n; i++) a[i] = _a[i];
  29.     }
  30.  
  31.     void build(int id, int l, int r)
  32.     {
  33.         if(l == r){
  34.             st2[id] = a[l];
  35.         }else{
  36.             int m = (l+r)/2;
  37.             build(id*2, l,m);
  38.             build(id*2 + 1, m+1, r);
  39.             st2[id] = min(st2[id*2], st2[id*2+1]);
  40.         }
  41.     }
  42.  
  43.     void update(int id,int l, int r, int pos)
  44.     {
  45.         if(l == r){
  46.             st1[id] = 1;
  47.         }else{
  48.             int m = (l+r)/2;
  49.             if(pos <=m){
  50.                 update(id*2,l,m,pos);
  51.             }else{
  52.                 update(id*2+1,m+1,r,pos);
  53.             }
  54.             st1[id] = st1[id*2] + st1[id*2 + 1];
  55.         }
  56.     }
  57.  
  58.     pair<int,int> get(int id, int l, int r, int u, int v)
  59.     {
  60.         if(r < u || v < l) return make_pair(0,inf);
  61.         if(u <= l && r<=v) return make_pair(st1[id], st2[id]);
  62.         int m = (l+r)/2;
  63.         pair<int,int> t1 = get(id*2,l,m,u,v);
  64.         pair<int,int> t2 = get(id*2+1,m+1,r,u,v);
  65.         return make_pair(t1.fi + t2.fi, min(t1.se, t2.se));
  66.     }
  67. };
  68.  
  69. void nhap()
  70. {
  71.     cin >> n >> q;
  72.     for(int i = 0; i<n-1; i++){
  73.         int a,b,c; cin >> a >> b >> c;
  74.         adj[a].pb(make_pair(b,c));
  75.         adj[b].pb(make_pair(a,c));
  76.     }
  77.     depth[1] = 0;
  78.     w[1] = 0;
  79.     parent[1] = 0;
  80. }
  81.  
  82. void dfs(int v, int par)
  83. {
  84.     treesize[v] = 1;
  85.     int index = -1;
  86.     int ans_index = -1;
  87.     for(pair<int,int> u : adj[v]){
  88.         ++index;
  89.         if(u.fi == par) continue;
  90.         parent[u.fi] = v;
  91.         w[u.fi] = u.se;
  92.         depth[u.fi] = depth[v] + 1;
  93.         dfs(u.fi, v);
  94.         treesize[v] += treesize[u.fi];
  95.         if(ans_index == -1 || treesize[u.fi] > treesize[adj[v][ans_index].fi]) ans_index = index;
  96.     }
  97.     if(ans_index != -1 && ans_index != 0 ) swap(adj[v][0], adj[v][ans_index]);
  98. }
  99.  
  100. void decompose(int v, int par, int h)
  101. {
  102.     head[v] = h;
  103.     pos[v] = ++cnt;
  104.     for(pair<int,int> u : adj[v]){
  105.         if(u.fi == par) continue;
  106.         if(u.fi == adj[v][0].fi){
  107.             decompose(u.fi,v,h);
  108.         }else{
  109.             decompose(u.fi,v,u.fi);
  110.         }
  111.     }
  112. }
  113.  
  114. void process()
  115. {
  116.     vector<int> a(n+1);
  117.     for(int i = 1; i<=n; i++) a[pos[i]] = w[i];
  118.     segtree st(n,a);
  119.     st.build(1,1,n);
  120.     while(q--)
  121.     {
  122.  
  123.     int type; cin >> type;
  124.  
  125.     if(type == 2){
  126.         int s; cin >> s;
  127.         st.update(1,1,n,pos[s]);
  128.     }else{
  129.         int u,v; cin >> u >> v;
  130.         if(u == v){
  131.             cout << 0 << endl;
  132.             continue;
  133.         }
  134.         bool flag = true;
  135.         int res = inf;
  136.         while(head[u] != head[v]){
  137.             if(depth[head[u]] < depth[head[v]]) swap(u,v);
  138.             pair<int,int> k = st.get(1,1,n,pos[head[u]],pos[u]);
  139.             if(k.fi != 0){
  140.                 flag = false;
  141.                 break;
  142.             }
  143.             res = min(res,k.se);
  144.             u = parent[head[u]];
  145.         }
  146.         if(depth[u] > depth[v]) swap(u,v);
  147.         pair<int,int> k = st.get(1,1,n,pos[u]+1,pos[v]);
  148.         res = min(res,k.se);
  149.         if(k.fi != 0) flag = false;
  150.         k = st.get(1,1,n,pos[u],pos[u]);
  151.         if(k.fi != 0) flag = false;
  152.         if(flag){
  153.             cout << res << endl;
  154.         }else{
  155.             cout << -1 << endl;
  156.         }
  157.     }
  158.  
  159.     }
  160. }
  161.  
  162. signed main()
  163. {
  164.     ios_base::sync_with_stdio(0); cin.tie(0);
  165. //    freopen("backup.inp","r",stdin);
  166. //    freopen("backup.out","w",stdout);
  167.     nhap();
  168.     dfs(1,-1);
  169.     decompose(1,-1,-1);
  170.     process();
  171.     return 0;
  172. }
  173.  
Success #stdin #stdout 0.01s 6816KB
comments (?)
stdin
copy 
4 4
1 2 3
2 3 4
2 4 2
1 3 4
2 2
1 3 4
1 1 1
stdout
copy 
2
-1
0
https://ideone.com/mOjtSn
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!