问题描述:

给定一棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成颜色c;
2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段)
请你写一个程序依次完成这m个操作。

输入:

第一行包含2个整数n和m,分别表示节点数和操作数;
第二行包含n个正整数表示n个节点的初始颜色
下面n-1行每行包含两个整数x和y,表示x和y之间有一条无向边。
下面m行每行描述一个操作:
“C a b c”表示这是一个染色操作,把节点a到节点b路径上所有点(包括a和b)都染成颜色c;
“Q a b”表示这是一个询问操作,询问节点a到节点b(包括a和b)路径上的颜色段数量。

输出:

对于每个询问操作,输出一行答案。

思路:

数据结构题。。。思维含量不高,要注意很多细节

首先对于树上路径的操作和询问一般不难想到用树剖。然后就考虑如果维护一个序列的颜色段数量,以及修改操作。这种序列问题一般用线段树维护,线段树节点储存:左端及右端颜色,区间颜色段总数,lazytag。up函数也稍微修改一下。这样就解决了在序列上的问题。

接着考虑树剖,对于树上区间的合并要注意特殊处理链的左右端点问题,要分别记录两条链的端点颜色,在合并时要分清是那一条链。

代码:

#include<bits/stdc++.h>
#define ls (root<<1)
#define rs (root<<1|1)
#define mid (l+r>>1)
#define MAXN 100005
using namespace std;

int n, m, ans, cnt, head[MAXN], w[MAXN];
int sum[MAXN*4], lcol[MAXN*4], rcol[MAXN*4], tag[MAXN*4];
int ind, Lcol, Rcol, val[MAXN], id[MAXN], f[MAXN], size[MAXN], dep[MAXN], son[MAXN], top[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void up(int root)
{
    sum[root]=sum[ls]+sum[rs];
    if(rcol[ls]==lcol[rs]) sum[root]--;
    lcol[root]=lcol[ls];
    rcol[root]=rcol[rs];
}

void down(int root, int l, int r)
{
    if(!tag[root]) return;
    sum[rs]=sum[ls]=1;
    lcol[ls]=rcol[ls]=tag[root];
    lcol[rs]=rcol[rs]=tag[root];
    tag[ls]=tag[rs]=tag[root];
    tag[root]=0;
}

void build(int root, int l, int r)
{
    if(l==r)
    {
        sum[root]=1;
        lcol[root]=rcol[root]=val[l];
        return;
    }
    build(ls, l, mid);
    build(rs, mid+1, r);
    up(root);
}

void update(int root, int l, int r, int x, int y, int k)
{
    if(l>y || r<x) return;
    if(l>=x && r<=y)
    {
        sum[root]=1;
        tag[root]=rcol[root]=lcol[root]=k;
        return;
    }
    down(root, l, r);
    update(ls, l, mid, x, y, k);
    update(rs, mid+1, r, x, y, k);
    up(root);
}

void query(int root, int l, int r, int x, int y)
{
    if (l>y || r<x) return;
    if(l==x) Lcol=lcol[root];
    if(r==y) Rcol=rcol[root];
    if(x<=l && y>=r)
    {
        ans+=sum[root];
        return;
    }
    down(root, l, r);
    query(ls, l, mid, x, y);
    query(rs, mid+1, r, x, y);
    if(mid>=x && mid+1<=y && rcol[ls]==lcol[rs]) ans--;
}

void dfs1(int x, int fa)
{
    int maxson=-1; f[x]=fa; size[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dep[to]=dep[x]+1;
        dfs1(to, x);
        size[x]+=size[to];
        if(size[to]>maxson) son[x]=to, maxson=size[to];
    }
}

void dfs2(int x, int topf)
{
    id[x]=++ind; val[ind]=w[x]; top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x], topf);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f[x] && to!=son[x]) dfs2(to, to);
    }
}

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

int query1(int x, int y)
{
    int last1=0, last2=0; ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x, y), swap(last1, last2);
        query(1, 1, n, id[top[x]], id[x]);
        if(Rcol==last1) ans--;
        last1=Lcol;
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y), swap(last1, last2);
    query(1, 1, n, id[x], id[y]);
    if(Lcol==last1) ans--;
    if(Rcol==last2) ans--;
    return ans;
}

int main()
{
    int x, y, a, b, c; char opt;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    for(int i=1; i<=m; i++)
    {
        scanf("%s%d%d", &opt, &a, &b);
        if(opt=='C') {scanf("%d", &c); update1(a, b, c);}
        if(opt=='Q') printf("%d\n", query1(a, b));
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注