2243: [SDOI2011]染色

Time Limit: 20 Sec  Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=2243

Description

Input

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面行每行描述一个操作：

“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

2

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 400001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

#define N 100001

int n,m,cnt,sz,head[N],deep[N],son[N],belong[N],pl[N],v[N],ft[N][];

bool vis[N];

struct seg

{

    int l,r,lc,rc,s,tag;

}t[maxn*];

struct edge

{

    int to,next;

}e[*maxn];

void insert(int u,int v)

{

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

    e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;

}

void dfs1(int x)

{

    vis[x]=son[x]=;

    for(int i=;i<=;i++)

    {

        if(deep[x]<(<<i))

            break;

        ft[x][i]=ft[ft[x][i-]][i-];

    }

    for(int i=head[x];i;i=e[i].next)

    {

        if(vis[e[i].to])

            continue;

        deep[e[i].to]=deep[x]+;

        ft[e[i].to][]=x;

        dfs1(e[i].to);

        son[x]+=son[e[i].to];

    }

}

void dfs2(int x,int chain)

{

    pl[x]=++sz;

    belong[x]=chain;

    int k=;

    for(int i=head[x];i;i=e[i].next)

        if(deep[e[i].to]>deep[x]&&son[k]<son[e[i].to])

            k=e[i].to;

    if(!k)

        return;

    dfs2(k,chain);

    for(int i=head[x];i;i=e[i].next)

        if(deep[e[i].to]>deep[x]&&k!=e[i].to)

            dfs2(e[i].to,e[i].to);

}

int lca(int x,int y)

{

    if(deep[x]<deep[y])

        swap(x,y);

    int t=deep[x]-deep[y];

    for(int i=;i<=;i++)

        if(t&(<<i))

            x=ft[x][i];

    for(int i=;i>=;i--)

        if(ft[x][i]!=ft[y][i])

        {

            x=ft[x][i];

            y=ft[y][i];

        }

    if(x==y)

        return x;

    return ft[x][];

}

void build(int k,int l,int r)

{

    t[k].l=l,t[k].r=r,t[k].s=,t[k].tag=-;

    if(l==r)

        return;

    int mid=(l+r)>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

}

void pushup(int k)

{

    t[k].lc=t[k<<].lc;t[k].rc=t[k<<|].rc;

    if(t[k<<].rc^t[k<<|].lc)t[k].s=t[k<<].s+t[k<<|].s;

    else t[k].s=t[k<<].s+t[k<<|].s-;

}

void pushdown(int k)

{

    int tmp=t[k].tag;t[k].tag=-;

    if(tmp==-||t[k].l==t[k].r)return;

    t[k<<].s=t[k<<|].s=;

    t[k<<].tag=t[k<<|].tag=tmp;

    t[k<<].lc=t[k<<].rc=tmp;

    t[k<<|].lc=t[k<<|].rc=tmp;

}

void change(int k,int x,int y,int c)

{

    pushdown(k);

    int l=t[k].l,r=t[k].r;

    if(l==x&&r==y)

    {t[k].lc=t[k].rc=c;t[k].s=;t[k].tag=c;return;}

    int mid=(l+r)>>;

    if(mid>=y)change(k<<,x,y,c);

    else if(mid<x)change(k<<|,x,y,c);

    else

    {

        change(k<<,x,mid,c);

        change(k<<|,mid+,y,c);

    }

    pushup(k);

}

int ask(int k,int x,int y)

{

    pushdown(k);

    int l=t[k].l,r=t[k].r;

    if(l==x&&r==y)return t[k].s;

    int mid=(l+r)>>;

    if(mid>=y)return ask(k<<,x,y);

    else if(mid<x)return ask(k<<|,x,y);

    else

    {

        int tmp=;

        if(t[k<<].rc^t[k<<|].lc)tmp=;

        return ask(k<<,x,mid)+ask(k<<|,mid+,y)-tmp;

    }

}

int getc(int k,int x)

{

    pushdown(k);

    int l=t[k].l,r=t[k].r;

    if(l==r)return t[k].lc;

    int mid=(l+r)>>;

    if(x<=mid)return getc(k<<,x);

    else return getc(k<<|,x);

}

int solvesum(int x,int f)

{

    int sum=;

    while(belong[x]!=belong[f])

    {

        sum+=ask(,pl[belong[x]],pl[x]);

        if(getc(,pl[belong[x]])==getc(,pl[ft[belong[x]][]]))sum--;

        x=ft[belong[x]][];

    }

    sum+=ask(,pl[f],pl[x]);

    return sum;

}

void solvechange(int x,int f,int c)

{

    while(belong[x]!=belong[f])

    {

        change(,pl[belong[x]],pl[x],c);

        x=ft[belong[x]][];

    }

    change(,pl[f],pl[x],c);

}

void solve()

{

    int a,b,c;

    dfs1();

    dfs2(,);

    build(,,n);

    for(int i=;i<=n;i++)

        change(,pl[i],pl[i],v[i]);

    for(int i=;i<=m;i++)

    {

        char ch[];

        scanf("%s",ch);

        if(ch[]=='Q')

        {

            scanf("%d%d",&a,&b);

            int t=lca(a,b);

            printf("%d\n",solvesum(a,t)+solvesum(b,t)-);

        }

        else

        {

            scanf("%d%d%d",&a,&b,&c);

            int t=lca(a,b);

            solvechange(a,t,c);solvechange(b,t,c);

        }

    }

}

void ini()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&v[i]);

    for(int i=;i<n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        insert(x,y);

    }

}

int main()

{

    ini();

    solve();

    return ;

}