fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define mod 1000000007
  4. #define lint long long int
  5. #define mp make_pair
  6. #define pb push_back
  7. #define lsb(x) ((x) & (-(x)))
  8. using namespace std;
  9.  
  10. class Aib {
  11. public:
  12.     vector <int> aib;
  13.  
  14.     Aib () {
  15.         aib.clear();
  16.     }
  17.  
  18.     void init (int n) {
  19.         aib.resize(n + 3, 0);
  20.     }
  21.  
  22.     void update (int pos, int val) {
  23.         pos ++;
  24.         for (; pos < aib.size(); pos += lsb(pos))
  25.             aib[pos] += val;
  26.     }
  27.  
  28.     int query (int pos) {
  29.         pos ++;
  30.         int ans = 0;
  31.         for (; pos; pos -= lsb(pos))
  32.             ans += aib[pos];
  33.         return ans;
  34.     }
  35.  
  36.     int query (int st, int dr) {
  37.         if (st > dr)
  38.             swap(st, dr);
  39.             st++;
  40.         return query(dr) - query(st - 1);
  41.     }
  42. };
  43.  
  44. class Path {
  45. public:
  46.     vector <int> path;
  47.     Aib aib;
  48. };
  49.  
  50. vector <Path> paths;
  51. int which_path[100005];
  52. int which_pos[100005];
  53.  
  54. int vertex_which_path[100005];
  55. int vertex_which_pos[100005];
  56.  
  57. vector <pair <int, int> > graph[100005];
  58. bitset <100005> vis;
  59.  
  60. void dfs (int node, int where) {
  61.     vertex_which_path[node] = where;
  62.     vertex_which_pos[node] = paths[where].path.size() - 1;
  63.     vis[node] = true;
  64.  
  65.     for (auto it: graph[node])
  66.         if (!vis[it.first]) {
  67.             paths[where].path.push_back(it.second);
  68.             dfs(it.first, where);
  69.         }
  70. }
  71.  
  72. int main()
  73. {
  74.     ios_base :: sync_with_stdio(false);
  75.     int n = 0;
  76.     cin >> n;
  77.  
  78.     int a, b;
  79.     for (int i = 1; i < n; i++) {
  80.         cin >> a >> b;
  81.  
  82.         graph[a].push_back(make_pair(b, i));
  83.         graph[b].push_back(make_pair(a, i));
  84.     }
  85.  
  86.     int center = 1;
  87.     for (int i = 1; i <= n; i++)
  88.         if (graph[i].size() > 2) {
  89.             center = i;
  90.             break;
  91.         }
  92.  
  93.     vis[center] = 1;
  94.     for (auto it: graph[center]) {
  95.         paths.push_back(Path());
  96.         paths.back().path.push_back(it.second);
  97.  
  98.         dfs(it.first, paths.size() - 1);
  99.     }
  100.  
  101.     int j;
  102.     for (int i = 0; i < paths.size(); i++) {
  103.         for (j = 0; j < paths[i].path.size(); j++) {
  104.             which_path[paths[i].path[j]] = i;
  105.             which_pos[paths[i].path[j]] = j;
  106.         }
  107.  
  108.         paths[i].aib.init(paths[i].path.size());
  109.     }
  110.  
  111.     vertex_which_path[center] = -1;
  112.  
  113.     int q = 0;
  114.     cin >> q;
  115.  
  116.     int tip, aux;
  117.     while (q--) {
  118.         cin >> tip >> a;
  119.  
  120.         if (tip == 1) {
  121.             paths[which_path[a]].aib.update(which_pos[a], -1);
  122.         }
  123.         else if (tip == 2) {
  124.             paths[which_path[a]].aib.update(which_pos[a], 1);
  125.         }
  126.         else if (tip == 3) {
  127.             cin >> b;
  128.  
  129.             if (vertex_which_path[a] == vertex_which_path[b] && a != center) {
  130.                 aux = paths[vertex_which_path[a]].aib.query(vertex_which_pos[a], vertex_which_pos[b]);
  131.  
  132.                 if (aux)
  133.                     cout << "-1\n";
  134.                 else
  135.                     cout << abs(vertex_which_pos[a] - vertex_which_pos[b]) << '\n';
  136.             }
  137.             else if (a != center && b != center){
  138.                 aux = paths[vertex_which_path[a]].aib.query(vertex_which_pos[a]) + paths[vertex_which_path[b]].aib.query(vertex_which_pos[b]);
  139.                 if (aux)
  140.                     cout << "-1\n";
  141.                 else
  142.                     cout << vertex_which_pos[a] + vertex_which_pos[b] + 2 << '\n';
  143.             }
  144.             else {
  145.                 if (a == center) {
  146.                     if (b == center) {
  147.                         cout << "0\n";
  148.                         continue ;
  149.                     }
  150.                     else
  151.                         swap(a, b);
  152.                 }
  153.  
  154.                 if (b == center) {
  155.                     aux = paths[vertex_which_path[a]].aib.query(vertex_which_pos[a]);
  156.                     if (aux)
  157.                         cout << "-1\n";
  158.                     else
  159.                         cout << vertex_which_pos[a] + 1 << '\n';
  160.                 }
  161.             }
  162.         }
  163.     }
  164.  
  165.     return 0;
  166. }
Success #stdin #stdout 0s 5980KB
comments (?)
stdin
copy 
7
1 5
6 4
2 3
3 5
5 6
3 7
1
3 4 2
stdout
copy 
5
https://ideone.com/4zEAUF
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!