SPOJ/GSS7.cc

   1 #include <cstdio>
   2 #include <algorithm>
   3
   4 using namespace std;
   5
   6 const int maxn = 1e5 + 10;
   7
   8 struct node {
   9   node *p, *ch[2];
  10   bool rev, flag;
  11   int val, lx, rx, mx, size, sum;
  12   inline bool dir() { return this == p->ch[1]; }
  13   inline bool isroot() { return !(this == p->ch[0] || this == p->ch[1]); }
  14   inline void setv(int x);
  15   inline void relax();
  16   inline void update();
  17 } pool[maxn], *nil = pool;
  18
  19 inline void node::setv(int x) {
  20   flag = true;
  21   val = x;
  22   sum = x * size;
  23   lx = rx = mx = max(0, x) * size;
  24 }
  25
  26 inline void node::relax() {
  27   if (rev) {
  28     swap(ch[0], ch[1]);
  29     swap(lx, rx);
  30     if (ch[0] != nil) ch[0]->rev ^= 1;
  31     if (ch[1] != nil) ch[1]->rev ^= 1;
  32     rev = false;
  33   }
  34   if (flag) {
  35     if (ch[0] != nil) ch[0]->setv(val);
  36     if (ch[1] != nil) ch[1]->setv(val);
  37     flag = false;
  38   }
  39 }
  40
  41 inline void node::update() {
  42   if (ch[0] != nil) ch[0]->relax();
  43   if (ch[1] != nil) ch[1]->relax();
  44   size = ch[0]->size + 1 + ch[1]->size;
  45   sum = ch[0]->sum + val + ch[1]->sum;
  46   lx = max(ch[0]->lx, ch[0]->sum + val + ch[1]->lx);
  47   rx = max(ch[1]->rx, ch[0]->rx + val + ch[1]->sum);
  48   mx = max(max(ch[0]->mx, ch[1]->mx), ch[0]->rx + val + ch[1]->lx);
  49 }
  50
  51 void rotate(node *u) {
  52   node *v = u->p;
  53   v->relax(), u->relax();
  54   int d = u->dir();
  55   u->p = v->p;
  56   if (!v->isroot()) v->p->ch[v->dir()] = u;
  57   if (u->ch[d^1] != nil) u->ch[d^1]->p = v;
  58   v->ch[d] = u->ch[d^1];
  59   u->ch[d^1] = v;
  60   v->p = u;
  61   v->update();
  62   u->update();
  63 }
  64
  65 void splay(node *u, node *target = nil) {
  66   u->relax();
  67   while (!u->isroot()) {
  68     if (u->p->isroot())
  69       rotate(u);
  70     else
  71       (u->dir() == u->p->dir()) ? (rotate(u->p), rotate(u)) : (rotate(u), rotate(u));
  72   }
  73   u->update();
  74 }
  75
  76 node* expose(node *u) {
  77   node *v;
  78   for (v = nil; u != nil; u = u->p) {
  79     splay(u);
  80     u->ch[1] = v;
  81     (v = u)->update();
  82   }
  83   return v;
  84 }
  85
  86 inline void evert(node *u) {
  87   expose(u)->rev ^= 1;
  88   splay(u);
  89 }
  90
  91 int main() {
  92   int n, op, a, b, c;
  93   scanf("%d", &n);
  94   nil->p = nil->ch[0] = nil->ch[1] = nil;
  95   for (int i = 1; i <= n; ++i) {
  96     scanf("%d", &pool[i].val);
  97     pool[i].ch[0] = pool[i].ch[1] = pool[i].p = nil;
  98     pool[i].update();
  99   }
 100   for (int i = 1; i < n; ++i) {
 101     scanf("%d%d", &a, &b);
 102     evert(pool + a);
 103     pool[a].p = pool + b;
 104   }
 105   int tcase;
 106   scanf("%d", &tcase);
 107   while (tcase--) {
 108     scanf("%d%d%d", &op, &a, &b);
 109     evert(pool + a);
 110     switch (op) {
 111       case 1:
 112         printf("%d\n", expose(pool + b)->mx);
 113         break;
 114       case 2:
 115         scanf("%d", &c);
 116         expose(pool + b)->setv(c);
 117         break;
 118     }
 119   }
 120   return 0;
 121 }