fork download
copy 
  1. #include <bits/stdc++.h>
  2. using ll = long long;
  3. using namespace std;
  4.  
  5. const ll maxn = 3e5 + 5;
  6.  
  7. struct T {
  8.     ll a, b;
  9. };
  10.  
  11. ll t, n, q;
  12. vector<vector<ll>> g(maxn, vector<ll>(0)), dp;
  13. vector<T> e(maxn);
  14. vector<bool> used(maxn);
  15.  
  16. void dfs(ll v, ll p = -1) {
  17.     for (auto i : g[v]) {
  18.         if (used[i]) continue;
  19.         ll to;
  20.         if (e[i].a == v) {
  21.             to = e[i].b;
  22.         } else {
  23.             to = e[i].a;
  24.         }
  25.         if (to == p) continue;
  26.         dfs(to, v);
  27.         dp[v][0] += max(dp[to][0], dp[to][1]);
  28.     }
  29.     for (auto i : g[v]) {
  30.         if (used[i]) continue;
  31.         ll to;
  32.         if (e[i].a == v) {
  33.             to = e[i].b;
  34.         } else {
  35.             to = e[i].a;
  36.         }
  37.         if (to == p) continue;
  38.         dp[v][1] = max(dp[v][1], dp[to][0] + 1 + dp[v][0] - max(dp[to][0], dp[to][1]));
  39.     }
  40. }
  41.  
  42. void sol() {
  43.     cin >> t >> n;
  44.     for (int i = 1; i <= n - 1; i++) {
  45.         ll a, b; cin >> a >> b;
  46.         e[i] = {a, b};
  47.         g[a].push_back(i);
  48.         g[b].push_back(i);
  49.     }
  50.     cin >> q;
  51.     while (q--) {
  52.         ll type; cin >> type;
  53.         if (type == 1) {
  54.             ll id; cin >> id;
  55.             used[id] = !used[id];
  56.         } else {
  57.             ll x; cin >> x;
  58.             dp.assign(maxn, vector<ll>(2, 0));
  59.             dfs(x);
  60.             cout << max(dp[x][0], dp[x][1]) << '\n';
  61.         }
  62.     }
  63. }
  64.  
  65. int main() {
  66.     //freopen("input.txt", "r", stdin);
  67.     //freopen("output.txt", "w", stdout);
  68.     ios::sync_with_stdio(0);
  69.     cin.tie(0);
  70.     ll tests = 1;
  71.     //cin >> tests;
  72.     while (tests--) sol();
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.03s 31256KB
comments (?)
stdin
copy 
0
8
1 2
2 3
2 4
4 5
1 6
6 7
7 8
8
1 7
2 1
1 7
2 1
1 3
2 3
1 5
2 6
stdout
copy 
3
4
3
1
https://ideone.com/ky0Uyj
language:
C++14 (gcc 8.3)
created:
15 days 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!