洛谷P2486 lct做法

题意：

给出一颗$n$个结点的无根树，处理$m$个操作，每个操作只会是如下两种之一：

（1）将结点$a$到$b$的路径上的所有点染成颜色$k$

（2）询问结点$a$到结点$b$的简单路径的颜色段数量

LCT方法：

$LCT$是用来维护动态增删边和树上路径的数据结构

对于每个$splay$，维护的是一条链，节点$x$在原树连接的是他在$splay$的前驱，不是$splay$的儿子，$x$的左子树是他之前的链，右子树是之后的链

对于路径$(x,y)$，先$split(x,y)$；

我们先考虑查询，$sum$保存当前$splay$的“连接处”的个数，即相邻颜色不一样的节点对数，答案即$tree[y].sum+1$，那么问题就到了如何在$push\_up$中维护这个值，显然，对节点$x$，$tree[x].sum=tree[son[0]].sum+tree[son[1]].sum+x$节点对他前后两段形成的“连接处个数”，一种方法是找前驱，即用传统$splay$的方法，但在$LCT$内由于$pre()$会调用$splay()$，$splay()$会调用$push_up()
$，$push_up$会调用$pre()$，循环递归，会出现错误。另一种方法是新增成员，来保存当前$splay$子树的最左端点和最右端点，这样贡献即$tree[x].color!=tree[tree[x].son[i]].colorr[i]$，此时$reverse()$也需要反转$tree[x].colorr[i]$

修改操作只需$split(x,y)$之后在$y$处下放标记即可了

#include
#define ll long long
using namespace std;

int n,q;

struct LCT
{
    struct node
    {
        int color,tag,sum,son[2],fa,lazy,colorr[2];
    };
    stack<int>s;
    vector<node>tree;
    LCT():tree(200005){}
    inline bool isroot(int x)
    {
        return tree[tree[x].fa].son[0]!=x&&tree[tree[x].fa].son[1]!=x;
    }
    inline int getson(int x,int y)
    {
        return x==tree[y].son[1];
    }
    inline void push_up(int x)
    {
        tree[x].sum=0;
		for(int i=0;i<=1;i++)
		{
			if(tree[x].son[i])
			{
				tree[x].sum+=tree[tree[x].son[i]].sum+(tree[x].color!=tree[tree[x].son[i]].colorr[!i]);
				tree[x].colorr[i]=tree[tree[x].son[i]].colorr[i];
			}
			else tree[x].colorr[i]=tree[x].color;
		}
    }
    inline void rotate(int x)
    {
        int y=tree[x].fa,z=tree[y].fa;
        int k1=getson(x,y),k2=getson(y,z);
        tree[x].fa=z;
        if(!isroot(y)) tree[z].son[k2]=x;
        tree[y].son[k1]=tree[x].son[!k1];
        if(tree[x].son[!k1]) tree[tree[x].son[!k1]].fa=y;
        tree[x].son[!k1]=y;
        tree[y].fa=x;
        push_up(y); push_up(x);
    }
    inline void reverse(int x)
    {
        swap(tree[x].son[0],tree[x].son[1]);
		swap(tree[x].colorr[0],tree[x].colorr[1]);
        tree[x].tag^=1;
    }
    inline void ccolor(int x,int k)
    {
        tree[x].lazy=k;
        tree[x].color=k;
        tree[x].sum=0;
		tree[x].colorr[0]=tree[x].colorr[1]=k;
    }
    void push_down(int x)
    {
        if(tree[x].tag)
        {
            for(int i=0;i<=1;i++)
                if(tree[x].son[i]) reverse(tree[x].son[i]);
            tree[x].tag=0;
        }
        if(tree[x].lazy)
        {
            for(int i=0;i<=1;i++)
                if(tree[x].son[i]) ccolor(tree[x].son[i],tree[x].lazy);
            tree[x].lazy=0;
        }
    }
    void splay(int x)
    {
        int now=x;
        s.push(now);
        while(!isroot(now))
        {
            s.push(tree[now].fa);
            now=tree[now].fa;
        }
        while(!s.empty())
        {
            push_down(s.top());
            s.pop();
        }
        while(!isroot(x))
        {
            int y=tree[x].fa,z=tree[y].fa;
            int k1=getson(x,y),k2=getson(y,z);
            if(!isroot(y))
            {
                if(k1==k2) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    inline void access(int x)//打通root->x的splay
    {
        int last=0;
        while(x)
        {
            splay(x);
            tree[x].son[1]=last;
            push_up(last=x);
            x=tree[x].fa;
        }
    }
    inline void makeroot(int x)
    {
        access(x);
        splay(x);
        reverse(x);
    }
    inline int findroot(int x)
    {
        access(x);
        splay(x);
        while(tree[x].son[0])
        {
            push_down(x);
            x=tree[x].son[0];
        }
        splay(x);
        return x;
    }
    inline void split(int x,int y)
    {
        makeroot(x);
        access(y);
        splay(y);
    }
    inline void link(int x,int y)
    {
        makeroot(x);
        tree[x].fa=y;
    }
}lct;

int main()
{
    cin>>n>>q;
    int nn=n;
    for(int i=1;i<=n;i++) scanf("%d",&lct.tree[i].color);
    for(int i=1;i<n;i++)
    {
        int u,v; scanf("%d%d",&u,&v);
        lct.link(u,v);
    }
    while(q--)
    {
        // lct.dfs();
        char s[5]; scanf("%s",s+1);
        if(s[1]=='Q')
        {
            int x,y; scanf("%d%d",&x,&y);
            lct.split(x,y);
            printf("%d\n",lct.tree[y].sum+1);
        }
        else
        {
            int x,y,k; scanf("%d%d%d",&x,&y,&k);
            lct.split(x,y); lct.ccolor(y,k);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172