2 条题解

  • 0
    @ 2025-10-9 21:02:14

    难点在如何用线段树实现染色。

    （以下讲述，端点是 dfs 树上的点，节点的线段树上的点）

    线段树结构体里面多定义 l_col 和 r_col，分别代表管辖范围左右端点的颜色。

    再定义个 cnt 表示当前节点管辖范围的颜色段数量。

    更新的时候比较左节点的 r_col 和右节点 l_col，如果一样 tr[p].cnt = 左右节点 cnt 和 - 1。

    不然就 tr[p].cnt = 左右节点 cnt。

    你以为这样就完了？

    发挥惊人的注意力，发现 get_sum 函数没那么简单，要返回一个结构体。

    node get_node(int p, int l, int r) {
	if (tr[p].r < l || tr[p].l > r) {
		return (node){0, 0, -1, -1, 0, -1};
	}
	if (l <= tr[p].l && tr[p].r <= r) {
		return tr[p];
	}
	
	pushdown(p);
	node res;
	node a = get_node(lc(p), l, r);
	node b = get_node(rc(p), l, r);
	res = merge(a, b);
	return res;
}

    我们考虑构造一个函数 merge，负责合并两个节点，和 pushup 差不多。

    node merge(node a, node b) {
	node res;
	if (a.cnt == 0) {
		return b;
	}
	if (b.cnt == 0) {
		return a;
	}
	
	res.l_col = a.l_col;
	res.r_col = b.r_col;
	
	res.cnt = a.cnt + b.cnt;
	if (a.r_col == b.l_col) {
		res.cnt --;
	}
	return res;
}

    同时 pushup 函数也应该保留，防止混乱。

    再来看询问路径函数：

    int query_path(int x, int y) {
	node t_x = {0, 0, -1, -1, 0, -1};
	node t_y = {0, 0, -1, -1, 0, -1};
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]]) {
			node no = get_node(1, dfn[top[x]], dfn[x]);
			t_x = merge(no, t_x);
			x = fa[top[x]];
		}
		else {
			node no = get_node(1, dfn[top[y]], dfn[y]);
			t_y = merge(no, t_y);
			y = fa[top[y]];
		}
	}
	
	if (dep[x] > dep[y]) {
		swap(x, y);
		swap(t_x, t_y);
	}
	node no = get_node(1, dfn[x], dfn[y]);
	node res = merge(no, t_y);
	swap(t_x.l_col, t_x.r_col);
	res = merge(t_x, res);
	return res.cnt;
}

    我们需要建两个结构体分别记录 x 和 y 的重链，防止混淆。

    最后合并时优先把同端点的合并。

    我们设一开始的 x y 就是 x y，while 之后的 x y 是 tx 和 ty。

    那么 t_x 就是 tx -> x 的链， t_y 就是 ty -> y 的链。

    （因为默认求重链就是 dfn 小的 -> dfn 大的）

    no 就是 tx - > ty 的链。

    那么我们先把 no 和 y 连起来变成 tx - > y，

    再把 t_x 的前后翻转，变成 x -> tx。

    最后 t_x 和 no 合并，x -> tx -> ty -> y。

    最后注意颜色初始化要等于 -1，懒标记只有不等于 -1 的时候才 pushup，

    pushup 和 pushdown 不要忘写了或者写多了，这道题应该就没问题。


    完整代码：

    #include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int num[N];
vector<int> G[N];
int fa[N], siz[N], son[N], dep[N];

void fir_dfs(int x, int x_fa) {
	fa[x] = x_fa;
	siz[x] = 1;
	son[x] = -1;
	dep[x] = dep[x_fa] + 1;
	
	for (int y : G[x]) if (y != x_fa) {
		fir_dfs(y, x);
		if ( (son[x] == -1) || (siz[son[x]] < siz[y]) ) {
			son[x] = y;
		}
		siz[x] += siz[y];
	}
}

int tsp, dfn[N], r_dfn[N], top[N];

void sec_dfs(int x, int tp) {
	tsp ++;
	dfn[x] = tsp;
	r_dfn[dfn[x]] = x;
	top[x] = tp;
	
	if (son[x] != -1) {
		sec_dfs(son[x], tp);
	}
	for (int y : G[x]) if (y != son[x] && y != fa[x]) {
		sec_dfs(y, y);
	}
}

#define lc(p) p << 1
#define rc(p) (p << 1) | 1

struct node {
	int l, r;
	int l_col, r_col;    // 左右端点的颜色 
	int cnt, lazy;    // 颜色段数量，懒标记
} tr[4 * N];

void pushup(int p) {
	tr[p].l_col = tr[lc(p)].l_col;
	tr[p].r_col = tr[rc(p)].r_col;
	tr[p].cnt = tr[lc(p)].cnt + tr[rc(p)].cnt;
	if (tr[lc(p)].r_col == tr[rc(p)].l_col) {
		tr[p].cnt --;
	}
}

void pushdown(int p) {
	if (tr[p].lazy != -1) {
		tr[lc(p)].l_col = tr[lc(p)].r_col = tr[p].lazy;
		tr[lc(p)].cnt = 1;
		tr[lc(p)].lazy = tr[p].lazy;
		
		tr[rc(p)].l_col = tr[rc(p)].r_col = tr[p].lazy;
		tr[rc(p)].cnt = 1;
		tr[rc(p)].lazy = tr[p].lazy;
		
		tr[p].lazy = -1; 
	}
}

void build(int p, int l, int r) {
	tr[p] = {l, r, -1, -1, r - l + 1, -1};   // 有关颜色的都一开始等于 -1 
	if (l == r) {
		tr[p].l_col = tr[p].r_col = num[r_dfn[l]];
		return ; 
	}
	
	int mid = (l + r) >> 1;
	build(lc(p), l, mid);
	build(rc(p), mid + 1, r);
	pushup(p);
}

void change(int p, int l, int r, int c) {
	if (tr[p].r < l || tr[p].l > r) {
		return ;
	}
	if (l <= tr[p].l && tr[p].r <= r) {
		tr[p].l_col = tr[p].r_col = c;
		tr[p].cnt = 1;
		tr[p].lazy = c;
		return ;
	}
	
	pushdown(p);
	change(lc(p), l, r, c);
	change(rc(p), l, r, c);
	pushup(p);
}

node merge(node a, node b) {
	node res;
	if (a.cnt == 0) {
		return b;
	}
	if (b.cnt == 0) {
		return a;
	}
	
	res.l_col = a.l_col;
	res.r_col = b.r_col;
	
	res.cnt = a.cnt + b.cnt;
	if (a.r_col == b.l_col) {
		res.cnt --;
	}
	return res;
}

node get_node(int p, int l, int r) {
	if (tr[p].r < l || tr[p].l > r) {
		return (node){0, 0, -1, -1, 0, -1};
	}
	if (l <= tr[p].l && tr[p].r <= r) {
		return tr[p];
	}
	
	pushdown(p);
	node res;
	node a = get_node(lc(p), l, r);
	node b = get_node(rc(p), l, r);
	res = merge(a, b);
	return res;
}

void change_path(int x, int y, int c) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) {
			swap(x, y);
		}
		change(1, dfn[top[x]], dfn[x], c);
		x = fa[top[x]];
	}
	
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	change(1, dfn[x], dfn[y], c);
}

int query_path(int x, int y) {
	node t_x = {0, 0, -1, -1, 0, -1};
	node t_y = {0, 0, -1, -1, 0, -1};
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]]) {
			node no = get_node(1, dfn[top[x]], dfn[x]);
			t_x = merge(no, t_x);
			x = fa[top[x]];
		}
		else {
			node no = get_node(1, dfn[top[y]], dfn[y]);
			t_y = merge(no, t_y);
			y = fa[top[y]];
		}
	}
	
	if (dep[x] > dep[y]) {
		swap(x, y);
		swap(t_x, t_y);
	}
	node no = get_node(1, dfn[x], dfn[y]);
	node res = merge(no, t_y);
	swap(t_x.l_col, t_x.r_col);
	res = merge(t_x, res);
	return res.cnt;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> num[i];
	}
	
	for (int i = 1; i < n; i ++) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	dep[0] = 0;
	fir_dfs(1, 0);
	tsp = 0;
	sec_dfs(1, 1);
	
	build(1, 1, n);
	
	for (int i = 1; i <= m; i ++) {
		char s[5];
		cin >> s;
		if (s[0] == 'C') {
			int x, y, c;
			cin >> x >> y >> c;
			change_path(x, y, c);
		}
		else {
			int x, y;
			cin >> x >> y;
			cout << query_path(x, y) << "\n";
		}
	}
	
	return 0;
}
    • 0
      @ 2025-10-8 17:06:11 
      #include <cstdio>
#include <algorithm>
using namespace std;
const int N=100005, M=N<<1;
struct edge{int y, pre;}a[M];int alen, last[N];
inline void ins(int x, int y){a[++alen]={y, last[x]};last[x]=alen;}
int b[N];
int dep[N], f[N], son[N], siz[N], top[N], dfn[N], rk[N], id;
void dfs(int x, int fa, int d){
    dep[x]=d;
    f[x]=fa;
    siz[x]=1;
    for(int k=last[x], y; k; k=a[k].pre){
        if((y=a[k].y)==fa)continue;
        dfs(y, x, d+1);
        siz[x]+=siz[y];
        if(siz[y]>siz[son[x]])son[x]=y;
    }
}
void dfs2(int x, int t){
    top[x]=t;
    dfn[x]=++id;
    rk[id]=x;
    if(!son[x])return;
    dfs2(son[x], t);
    for(int k=last[x], y; k; k=a[k].pre)
        if((y=a[k].y)!=son[x]&&y!=f[x])
            dfs2(y, y);
}
struct node{
    int l, r, s;
    friend inline node operator+(node x, node y){
        if(!x.s)return y;
        if(!y.s)return x;
        return {x.l, y.r, x.s+y.s-(x.r==y.l)};
    }
};
struct trnode{int l, r, lc, rc; node d;}tr[M];int trlen;
#define ls(x) tr[x].lc
#define rs(x) tr[x].rc
inline void pushup(int x){tr[x].d=tr[ls(x)].d+tr[rs(x)].d;}
inline void pushdown(int x){if(tr[x].d.s==1)tr[ls(x)].d=tr[rs(x)].d=tr[x].d;}
int build(int l, int r){
    int now=++trlen;
    tr[now]={l, r, -1, -1, {0,0,0}};
    if(l==r)return tr[now].d={b[rk[l]], b[rk[l]], 1}, now;
    int mid=(l+r)>>1;
    ls(now)=build(l, mid);
    rs(now)=build(mid+1, r);
    pushup(now);
    return now;
}
void change(int now, int l, int r, int c){
    if(tr[now].l==l&&tr[now].r==r)return tr[now].d={c, c, 1}, void();
    pushdown(now);
    int mid=(tr[now].l+tr[now].r)>>1;
    if(r<=mid)change(ls(now), l, r, c);
    else if(mid+1<=l)change(rs(now), l, r, c);
    else change(ls(now), l, mid, c), change(rs(now), mid+1, r, c);
    pushup(now);
}
node query(int now, int l, int r){
    if(tr[now].l==l&&tr[now].r==r)return tr[now].d;
    pushdown(now);
    int mid=(tr[now].l+tr[now].r)>>1;
    if(r<=mid)return query(ls(now), l, r);
    if(mid+1<=l)return query(rs(now), l, r);
    return query(ls(now), l, mid)+query(rs(now), mid+1, r);
}
void change(int x, int y, int c){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x, y);
        change(1, dfn[top[x]], dfn[x], c);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])swap(x, y);
    change(1, dfn[x], dfn[y], c);
}
int query(int x, int y){
    node s1={0,0,0}, s2={0,0,0};
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x, y), swap(s1, s2);
        s1=query(1, dfn[top[x]], dfn[x])+s1;
        x=f[top[x]];
    }
    if(dep[x]>dep[y])s1=query(1, dfn[y], dfn[x])+s1;
    else s2=query(1, dfn[x], dfn[y])+s2;
    swap(s1.l, s1.r);
    return (s1+s2).s;
}
char s[5];
int main(){
    int n, m;scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i)scanf("%d", &b[i]);
    for(int i=1, x, y; i<n; ++i){
        scanf("%d%d", &x, &y);
        ins(x, y);ins(y, x);
    }
    dfs(1, 0, 1);dfs2(1, 1);
    build(1, n);
    for(int i=1, x, y, c; i<=m; ++i){
        scanf("%s%d%d", s, &x, &y);
        if(s[0]=='C')scanf("%d", &c), change(x, y, c);
        else printf("%d\n", query(x, y));
    }
    return 0;
}
      • 1

      【树链剖分】[SDOI2011] 染色

      信息

      ID
      3908
      时间
      1000ms
      内存
      128MiB
      难度
      10
      标签
      递交数
      8
      已通过
      5
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 10ms
      4. Powered by Hydro v5.0.1 Community