SPOJ/QTREE7.cc

   1 #include <cstdio>
   2 #include <climits>
   3 #include <vector>
   4 #include <algorithm>
   5
   6 const int N = 100000 + 10, LOG = 20;
   7
   8 int n, col[N];
   9 std::vector<int> adj[N];
  10
  11 int fa[LOG][N], dep[N], left[N], right[N];
  12 std::vector<int> dfn;
  13
  14 void DFS(int a) {
  15   for (std::vector<int>::iterator it = adj[a].begin(); it != adj[a].end(); ++it) {
  16     int b = *it;
  17     if (b != fa[0][a]) {
  18       fa[0][b] = a;
  19       dep[b] = dep[a] + 1;
  20       left[b] = dfn.size();
  21       dfn.push_back(b);
  22       DFS(b);
  23       right[b] = dfn.size();
  24       dfn.push_back(b);
  25     }
  26   }
  27 }
  28
  29 class EulerTourTree {
  30
  31   class node_t {
  32     inline int dir() {
  33       if (!p) return -1;
  34       return this == p->ch[1];
  35     }
  36
  37     inline void rotate() {
  38       node_t *u = p;
  39       int d = dir();
  40       u->p->setc(this, u->dir());
  41       u->setc(ch[!d], d);
  42       setc(u, !d);
  43       u->update();
  44       update();
  45     }
  46
  47    public:
  48     node_t *p, *ch[2];
  49     int mx, val;
  50
  51     inline void setc(node_t *c, int d) {
  52       if (this) ch[d] = c;
  53       if (c) c->p = this;
  54     }
  55
  56     inline void update() {
  57       mx = val;
  58       if (ch[0]) mx = std::max(mx, ch[0]->mx);
  59       if (ch[1]) mx = std::max(mx, ch[1]->mx);
  60     }
  61
  62     inline void splay(node_t *target = NULL) {
  63       while (p != target) {
  64         if (p->p != target) (dir() == p->dir() ? p : this)->rotate();
  65         rotate();
  66       }
  67     }
  68   } pool[2 * N];
  69
  70  public:
  71   void init() {
  72     for (int i = 0; i <= n; ++i) {
  73       pool[left[i]].setc(pool + right[i], 1);
  74       pool[left[i]].update();
  75     }
  76   }
  77
  78   void link(int u) {
  79     int v = fa[0][u];
  80     pool[left[v]].splay();
  81     pool[right[v]].splay(pool + left[v]);
  82     pool[left[u]].splay();
  83     pool[right[u]].splay(pool + left[u]);
  84     pool[left[v]].setc(pool + left[u], 1);
  85     pool[right[u]].setc(pool + right[v], 1);
  86     pool[right[v]].splay();
  87   }
  88
  89   void cut(int u) {
  90     pool[left[u]].splay();
  91     pool[right[u]].splay(pool + left[u]);
  92     node_t *x = pool[left[u]].ch[0], *y = pool[right[u]].ch[1];
  93     pool[left[u]].ch[0] = x->p = NULL;
  94     pool[right[u]].ch[1] = y->p = NULL;
  95     pool[right[u]].update();
  96     pool[left[u]].update();
  97     if (!x || !y) return;
  98     while (x->ch[1]) x = x->ch[1];
  99     x->splay();
 100     x->setc(y, 1);
 101     x->update();
 102   }
 103
 104   void modify(int u, int w) {
 105     pool[left[u]].val = pool[right[u]].val = w;
 106     pool[left[u]].splay();
 107     pool[right[u]].splay();
 108   }
 109
 110   int query(int u) {
 111     node_t *temp = pool + left[u];
 112     for (temp->splay(); temp->ch[0];) temp = temp->ch[0];
 113     int x = dfn[temp - pool], y = u;
 114     for (int i = LOG - 1; i >= 0; --i)
 115       if (~fa[i][y] && dep[fa[i][y]] > dep[x])
 116         y = fa[i][y];
 117     pool[left[y]].splay();
 118     pool[right[y]].splay(pool + left[y]);
 119     node_t *z = pool[right[y]].ch[0];
 120     return std::max(z ? z->mx : INT_MIN, pool[left[y]].val);
 121   }
 122
 123 } tree[2];
 124
 125 int main() {
 126   scanf("%d", &n);
 127   for (int ecnt = n - 1, u, v; ecnt--;) {
 128     scanf("%d%d", &u, &v);
 129     adj[u].push_back(v);
 130     adj[v].push_back(u);
 131   }
 132   adj[0].push_back(1);
 133   left[0] = 0;
 134   dfn.push_back(0);
 135   DFS(0);
 136   right[0] = dfn.size();
 137   dfn.push_back(0);
 138   tree[0].init();
 139   tree[1].init();
 140   for (int i = 1; i <= n; ++i) {
 141     scanf("%d", col + i);
 142     tree[col[i]].link(i);
 143   }
 144   for (int i = 1, w; i <= n; ++i) {
 145     scanf("%d", &w);
 146     tree[0].modify(i, w);
 147     tree[1].modify(i, w);
 148   }
 149   fa[0][0] = -1;
 150   for (int j = 1; j < LOG; ++j)
 151     for (int i = 1; i <= n; ++i)
 152       fa[j][i] = fa[j - 1][fa[j - 1][i]];
 153   int tcase;
 154   for (scanf("%d", &tcase); tcase--;) {
 155     int op, u, w;
 156     scanf("%d%d", &op, &u);
 157     switch (op) {
 158       case 0:
 159         printf("%d\n", tree[col[u]].query(u));
 160         break;
 161       case 1:
 162         tree[col[u]].cut(u);
 163         tree[col[u] ^= 1].link(u);
 164         break;
 165       case 2:
 166         scanf("%d", &w);
 167         tree[0].modify(u, w);
 168         tree[1].modify(u, w);
 169         break;
 170     }
 171   }
 172   return 0;
 173 }