题目链接：

• 洛谷 P2486
• BZOJ P2243

方法

可以想到，颜色段的个数也是具有可加性的，但是如果两段连接处（即线段树中左子树的最右边的点和右子树的最左端的点）的颜色是相同的话，中间就只能算作一段，需要将颜色段个数-1。

所以我们在线段树里多加两个变量，分别为这一段最左端的点颜色和最右端的颜色，合并时和查询时判断一下即可。

注意的是查询链上时也需要判断。每次查询时记录一下左端点颜色，每一次判断一下当前剖到的右端点与上一次剖到的左端点是否相同即可。又由于有u和v两个节点要不停交换，所以用lastc1和lastc2两个变量来存上一次的左端点颜色，当u和v交换时，lastc1和lastc2也需要对应交换。当u和v在一条链上的时候，两边端点都需要比较。

查询链时代码

int qrange(int u,int v)
{
    int ans=0,lastc1=lastc2=-1;
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) 
        {
            swap(u,v);
            swap(lastc1,lastc2);//同时交换
        }
        ans+=query(1,id[top[u]],id[u]+1);
        if (rcol==lastc1) ans--;//将当前右端点同上一次左端点比较
        lastc1=lcol;
        u=fa[top[u]];
    }
    if (deep[u]<deep[v]) //注意交换顺序，不要弄反
    {
        swap(u,v);
        swap(lastc1,lastc2);
    }
    ans+=query(1,id[v],id[u]+1);
    if (rcol==lastc1) ans--;
    if (lcol==lastc2) ans--;//都要比较
    return ans;
}

其中lcol和rcol在query函数中就顺便获得了

其它的就是标准的树链剖分了。传送门：树链剖分总结 - Llf’s blog

代码

同样，我的线段树是[left,right)形式，调用时要将右边端点+1

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
struct Edge{
    int next,to;
} edge[MAXN];
struct Tree{
    int left,right,leftc,rightc,sum,delta;//leftc和rightc分别是左右端点颜色
} tree[MAXN*4];
int deep[MAXN],top[MAXN],son[MAXN],fa[MAXN],size[MAXN],id[MAXN],w[MAXN],wnew[MAXN],head[MAXN];
int n,m,a,b,c,cnt=1,dfsord,rcol,lcol,lastc1,lastc2;
inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void add(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
inline void pushup(int x)
{
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
    if (tree[x*2].rightc==tree[x*2+1].leftc) tree[x].sum--;
    tree[x].leftc=tree[x*2].leftc;
    tree[x].rightc=tree[x*2+1].rightc;
}
inline void update(int x)
{
    tree[x*2].sum=tree[x*2+1].sum=1;
    tree[x*2].leftc=tree[x*2].rightc=tree[x*2+1].leftc=tree[x*2+1].rightc=tree[x].delta;
    tree[x*2].delta=tree[x*2+1].delta=tree[x].delta;
    tree[x].delta=0;
}
void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    tree[x].delta=0;
    if (r-l==1) 
    {
        tree[x].leftc=tree[x].rightc=wnew[l];
        tree[x].sum=1;
    }
    else
    {
        build(x*2,l,(l+r)/2);
        build(x*2+1,(l+r)/2,r);
        pushup(x);
    }
}
void change(int x,int l,int r,int delta)
{
    if (l<=tree[x].left && r>=tree[x].right)
    {
        tree[x].sum=1;
        tree[x].leftc=tree[x].rightc=delta;
        tree[x].delta=delta;
    }
    else
    {
        if (tree[x].delta!=0) update(x);
        if (l<(tree[x].left+tree[x].right)/2) change(x*2,l,r,delta);
        if (r>(tree[x].left+tree[x].right)/2) change(x*2+1,l,r,delta);
        pushup(x);
    }
}
int query(int x,int l,int r)
{
    if (l<=tree[x].left && r>=tree[x].right) 
    {
        if (l==tree[x].left) lcol=tree[x].leftc;
        if (r==tree[x].right) rcol=tree[x].rightc;
        return tree[x].sum;
    }
    else
    {
        if (tree[x].delta!=0) update(x);
        int ans=0;
        if (l<(tree[x].left+tree[x].right)/2) ans+=query(x*2,l,r);
        if (r>(tree[x].left+tree[x].right)/2) ans+=query(x*2+1,l,r);
        if (tree[x*2].rightc==tree[x*2+1].leftc && l<(tree[x].left+tree[x].right)/2 && r>(tree[x].left+tree[x].right)/2) ans--;
        return ans;
    }
}
void dfs1(int x,int f,int dep)
{
    deep[x]=dep;
    fa[x]=f;
    size[x]=1;
    int mx=-1;
    for (int i=head[x];i!=-1;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs1(y,x,dep+1);
        size[x]+=size[y];
        if (size[y]>mx) 
        {
            mx=size[y];
            son[x]=y;
        }
    }
}
void dfs2(int x,int topf)
{
    top[x]=topf;
    id[x]=++dfsord;
    wnew[dfsord]=w[x];
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (int i=head[x];i!=-1;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}
void uprange(int u,int v,int delta)
{
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        change(1,id[top[u]],id[u]+1,delta);
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    change(1,id[u],id[v]+1,delta);
}
int qrange(int u,int v)
{
    int ans=0,lastc1=lastc2=-1;
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) 
        {
            swap(u,v);
            swap(lastc1,lastc2);
        }
        ans+=query(1,id[top[u]],id[u]+1);
        if (rcol==lastc1) ans--;
        lastc1=lcol;
        u=fa[top[u]];
    }
    if (deep[u]<deep[v]) 
    {
        swap(u,v);
        swap(lastc1,lastc2);
    }
    ans+=query(1,id[v],id[u]+1);
    if (rcol==lastc1) ans--;
    if (lcol==lastc2) ans--;
    return ans;
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read();m=read();
    for (int i=1;i<=n;i++) w[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read();b=read();
        add(a,b);
        add(b,a);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n+1);
    for (int i=1;i<=m;i++)
    {
        char x;
        cin>>x;
        if (x=='C')
        {
            a=read();b=read();c=read();
            uprange(a,b,c);
        }
        else
        {
            a=read();b=read();
            printf("%d\n",qrange(a,b));
        }
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/luogu-solution-p2486.html