BZOJ_1036

​​題目連結​​。題目的大意就是在樹上修改和查詢相關的資訊。看到這個其實我們很容易的想到線段樹，如果是在數組上也就是線性結構中實作這些操作，其實很簡單，就是線段樹的基本功能。但是由于資料的的形式的組織的改變，使得線段樹不能再直接的使用。那麼如何在樹上完成這些操作呢？

其實思考問題都是有這樣的一個過程：将未知轉化為已知。我麼知道支援修改和查詢，線段是是一個很好的工具。是以我們會有一個很原始的想法，能不能繼續使用這種資料結構來維護資料，那麼我們就面臨一個問題，線段樹隻能維護線性的資料結構，是以我們就要把樹形的資料轉化為線性的。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
#define MAXN 30010
int head[MAXN];
struct node 
{
  int y, next;
}edge[2 * MAXN];
int id[MAXN], son[MAXN], dep[MAXN], fa[MAXN], siz[MAXN], a[MAXN];
int l, x, y, n, q, tot;
char s[10];
int pre[MAXN], top[MAXN];
void add(int x, int y)
{
  l++;
  edge[l].y = y;
  edge[l].next = head[x];
  head[x] = l;
}
void dfs1(int x, int f)
{
  int y;
  fa[x] = f;
  son[x] = 0;
  siz[x] = 1;
  for (int i = head[x]; i != -1; i = edge[i].next)
    if (edge[i].y != f)
    {
      y = edge[i].y;
      dep[y] = dep[x] + 1;
      dfs1(y, x);
      siz[x] += siz[y];
      if (siz[son[x]]<siz[y])
        son[x] = y;
    }
}
void dfs2(int x, int tp)
{
  int y;
  top[x] = tp;
  id[x] = ++tot;// tot is the total number
  pre[id[x]] = x;
  if (son[x]) dfs2(son[x], tp);
  for (int i = head[x]; i != -1; i = edge[i].next)
    if (edge[i].y != fa[x] && edge[i].y != son[x])
    {
      y = edge[i].y;
      dfs2(y, y);
    }
}
struct point
{
  int l, r, sum, max;
}tr[4 * MAXN];
void updata(int p)
{
  tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
  tr[p].max = max(tr[p << 1].max, tr[p << 1 | 1].max);
}
void build(int p, int l, int r)
{
  tr[p].l = l; tr[p].r = r;
  if (l == r) { tr[p].sum = tr[p].max = a[pre[l]]; return; }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
  updata(p);
}
void change(int p, int x, int y)
{
  if (tr[p].l == x && tr[p].r == x)
  {
    tr[p].sum = tr[p].max = y;
    return;
  }
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (x <= mid) change(p << 1, x, y);
  if (x>mid) change(p << 1 | 1, x, y);
  updata(p);
}
int ask_max(int p, int l, int r)
{
  if (tr[p].l == l && tr[p].r == r)
    return tr[p].max;
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (r <= mid) return ask_max(p << 1, l, r);
  if (l>mid) return ask_max(p << 1 | 1, l, r);
  if (l <= mid && r>mid)
  {
    int s1 = ask_max(p << 1, l, mid);
    int s2 = ask_max(p << 1 | 1, mid + 1, r);
    return max(s1, s2);
  }
}
int ask_sum(int p, int l, int r)
{
  if (tr[p].l == l && tr[p].r == r)
    return tr[p].sum;
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (r <= mid) return ask_sum(p << 1, l, r);
  if (l>mid) return ask_sum(p << 1 | 1, l, r);
  if (l <= mid && r>mid)
  {
    int s1 = ask_sum(p << 1, l, mid);
    int s2 = ask_sum(p << 1 | 1, mid + 1, r);
    return s1 + s2;
  }
}
int find_max(int x, int y)
{
  int f1 = top[x], f2 = top[y], tmp = -0x3f3f3f;//有負數
  while (f1 != f2)
  {
    if (dep[f1]<dep[f2])
    {
      swap(f1, f2); swap(x, y);
    }
    tmp = max(tmp, ask_max(1, id[f1], id[x]));
    x = fa[f1]; f1 = top[x];
  }
  if (x == y) return max(tmp, ask_max(1, id[x], id[x]));
  if (dep[x]>dep[y]) swap(x, y);
  return max(tmp, ask_max(1, id[x], id[y]));
}
int find_sum(int x, int y)
{
  int f1 = top[x], f2 = top[y], tmp = 0;
  while (f1 != f2)
  {
    if (dep[f1]<dep[f2])
    {
      swap(f1, f2); swap(x, y);
    }
    tmp += ask_sum(1, id[f1], id[x]);
    x = fa[f1]; f1 = top[x];
  }
  if (x == y) return tmp + ask_sum(1, id[x], id[y]);
  if (dep[x]>dep[y]) swap(x, y);
  return tmp + ask_sum(1, id[x], id[y]);
}
int main()
{
  scanf("%d", &n);
  memset(head, -1, sizeof(head));
  for (int i = 1; i<n; i++)
  {
    scanf("%d%d", &x, &y);
    add(x, y);
    add(y, x);
  }
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  dfs1(1, 0);
  dfs2(1, 1);
  build(1, 1, n);
  scanf("%d", &q);
  while (q--)
  {
    scanf("%s%d%d", s, &x, &y);
    if (s[0] == 'C')  change(1, id[x], y);
    if (s[0] == 'Q' && s[1] == 'M') printf("%d\n", find_max(x, y));
    if (s[0] == 'Q' && s[1] == 'S') printf("%d\n", find_sum(x, y));//if there is X types of queries, we need to write X parts for the queries
  }
}