P2486

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;
int n,m,a,b,c,cnt,tot,lx,ly,t1,t2;
int v[N],head[N],nxt[N],e[N],fa[N],dep[N],siz[N],son[N],id[N],top[N],rev[N];
struct Tree
{
  int l,r,sum,tag;
} tr[4*N];
char ch;

void add_edge(int x,int y)
{
  tot++;
  e[tot] = y;
  nxt[tot] = head[x],head[x] = tot;
}

void dfs1(int x,int f)
{
  fa[x] = f;
  dep[x] = dep[f] + 1;
  siz[x] = 1;
  for(int i = head[x]; i; i = nxt[i])
  {
    if(e[i] == f) continue;
    dfs1(e[i],x);
    siz[x] += siz[e[i]];
    if(siz[e[i]] > siz[son[x]]) son[x] = e[i];
  }
}

void dfs2(int x,int y)
{
  id[x] = ++cnt;
  top[x] = y;
  rev[cnt] = x;
  if(!son[x]) return ;
  dfs2(son[x],y);
  for(int i = head[x]; i; i = nxt[i])
  {
    if(e[i] == fa[x] || e[i] == son[x]) continue;
    dfs2(e[i],e[i]);
  }
}

void color(int x,int y)
{
  tr[x].sum = 1;
  tr[x].l = tr[x].r = y;
  tr[x].tag = y;
}

void updup(int id)
{
  tr[id].sum = tr[id * 2].sum + tr[id * 2 + 1].sum;
  if(tr[id * 2].r == tr[id * 2 + 1].l) tr[id].sum--;
  tr[id].l = tr[id * 2].l,tr[id].r = tr[id * 2 + 1].r;
}

void upddown(int id)
{
  if(tr[id].tag)
  {
    color(id * 2,tr[id].tag);
    color(id * 2 + 1,tr[id].tag);
    tr[id].tag = 0;
  }
}

void build(int id,int l,int r)
{
  if(l == r)
  {
    tr[id].sum = 1;
    tr[id].l = tr[id].r = v[rev[l]];
    return ;
  }
  build(id * 2,l,(l + r) / 2);
  build(id * 2 + 1,(l + r) / 2 + 1,r);
  updup(id);
}

void update(int id,int l,int r,int x,int y,int z)
{
  if(x <= l && r <= y)
  {
    color(id,z);
    return ;
  }
  upddown(id);
  int mid = (l + r) / 2;
  if(x <= mid) update(id * 2,l,mid,x,y,z);
  if(y > mid) update(id * 2 + 1,mid + 1,r,x,y,z);
  updup(id);
}

int query(int id,int l,int r,int x,int y)
{
  if(x <= l && r <= y)
  {
    if(x == l) t1 = tr[id].l;
    if(y == r) t2 = tr[id].r;
    return tr[id].sum;
  }
  int mid = (l + r) / 2;
  if(y <= mid) return query(id * 2,l,mid,x,y);
  if(x > mid) return query(id * 2 + 1,mid + 1,r,x,y);
  int ret = query(id * 2,l,mid,x,y) + query(id * 2 + 1,mid + 1,r,x,y);
  if(tr[id * 2].r == tr[id * 2 + 1].l) ret--;
  return ret;
}

void upd(int x,int y,int z)
{
  while(top[x] != top[y])
  {
    if(dep[top[x]] < dep[top[y]]) swap(x,y);
    update(1,1,n,id[top[x]],id[x],z);
    x = fa[top[x]];
  }
  if(id[x] > id[y]) swap(x,y);
  update(1,1,n,id[x],id[y],z);
}

void que(int x,int y)
{
  int sum = 0;
  lx = 0,ly = 0;
  while(top[x] != top[y])
  {
    if(dep[top[x]] < dep[top[y]])
    {
      swap(x,y);
      swap(lx,ly);
    }
    sum += query(1,1,n,id[top[x]],id[x]);
    if(t2 == lx) sum--;
    lx = t1;
    x = fa[top[x]];
  }
  if(id[x] > id[y])
  {
    swap(x,y);
    swap(lx,ly);
  }
  sum += query(1,1,n,id[x],id[y]);
  if(lx == t1) sum--;
  if(ly == t2) sum--;
  printf("%d\n",sum);
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i = 1; i <= n; i++) scanf("%d",&v[i]);
  for(int i = 1; i < n; i++)
  {
    scanf("%d%d",&a,&b);
    add_edge(a,b);
  }
  dfs1(1,0);
  dfs2(1,1);
  build(1,1,n);
  while(m--)
  {
    ch = getchar();
    while(ch != 'C' && ch != 'Q') ch = getchar();
    if(ch == 'C')
    {
      scanf("%d%d%d",&a,&b,&c);
      upd(a,b,c);
    }
    else
    {
      scanf("%d%d",&a,&b);
      que(a,b);
    }
  }
  //while(1);
  return 0;
}

求助大佬