P3703 [SDOI2017]树点涂色 LCT维护颜色+线段树维护dfs序+倍增LCA

\(\color{#0066ff}{ 题目描述 }\)

Bob有一棵\(n\)个点的有根树,其中1号点是根节点。Bob在每个点上涂了颜色,并且每个点上的颜色不同。

定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。

Bob可能会进行这几种操作:

  • 1 x

把点\(x\)到根节点的路径上所有的点染上一种没有用过的新颜色。

  • 2 x y

求\(x\)到\(y\)的路径的权值。

  • 3 x

在以x为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob一共会进行\(m\)次操作

\(\color{#0066ff}{输入格式}\)

第一行两个数\(n,m\)。

接下来\(n-1\)行,每行两个数\(a,b\),表示\(a\)与\(b\)之间有一条边。

接下来\(m\)行,表示操作,格式见题目描述

\(\color{#0066ff}{输出格式}\)

每当出现2,3操作,输出一行。

如果是2操作,输出一个数表示路径的权值

如果是3操作,输出一个数表示权值的最大值

\(\color{#0066ff}{输入样例}\)

5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5

\(\color{#0066ff}{输出样例}\)

3
4
2
2

\(\color{#0066ff}{数据范围与提示}\)

共10个测试点

测试点1,\(1\leq n,m\leq1000\)

测试点2、3,没有2操作

测试点4、5,没有3操作

测试点6,树的生成方式是,对于i(\(2\leq i \leq n\))i(2≤i≤n),在1到\(i-1\)中随机选一个点作为i的父节点。

测试点7,\(1\leq n,m\leq 50000\)

测试点8,\(1\leq n \leq 50000\)

测试点9,10,无特殊限制

对所有数据,\(1\leq n \leq 10^5\),\(1\leq m \leq 10^5\)

时间限制:1s

空间限制:128MB

\(\color{#0066ff}{ 题解 }\)

震惊!这题能用LCT,蒟蒻刚拿到这题一脸懵逼。。。

怎么用LCT维护颜色呢。。。显然不能每种颜色都一个LCT吧。。(MLE。。)

诶,不能每种颜色一个LCT,每种颜色一个Splay呢,这是可以的吧。。。

正好发现一个东西,每时每刻颜色相同的点一定是一条深度严格递增的链!

于是。。。真的就每个颜色一个Splay了

现在开始考虑操作

第一个操作,显然access就行了。。。

第二个操作, 我们肯定是不能琛出x到y的链的,这样就乱了

那么LCT就维护不了这个东西了。但是没有LCT还要支持两个点的询问。。。

复杂度保证的情况下只有树上差分了吧(\(ans[x]+ans[y]-ans[lca]\))

我们记\(f[x]\)为x到根的答案,那么x到y的答案就是\(f[x]+f[y]-2*f[lca]+1\)

加1是因为LCA被减两次

这个LCA显然只能倍增了。。LCT是动不了的

然后你这\(f\)咋求啊?

初始的时候肯定是深度没错, 实际上它就是x到根的虚边的个数+1

因此在access的时候就能修改

可是,虚实变换的时候,影响的是一棵子树啊, 这是子树修改

于是。。。线段树维护个dfs序就可以完美的解决

然后第三个操作,就是线段树上区间max,就没了。。。

#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 1e5 + 10;
struct node {
node *ch[2], *fa;
node() { ch[0] = ch[1] = fa = NULL; }
bool isr() { return this == fa->ch[1]; }
bool ntr() { return fa && (fa->ch[0] == this || fa->ch[1] == this); }
}pool[maxn];
struct Tree {
Tree *ch[2];
int l, r, max, tag;
Tree(int l = 0, int r = 0, int max = 0, int tag = 0): l(l), r(r), max(max), tag(tag) {}
void trn(int val) { max += val, tag += val; }
void upd() { max = std::max(ch[0]->max, ch[1]->max); }
void dwn() {
if(!tag) return;
ch[0]->trn(tag);
ch[1]->trn(tag);
tag = 0;
}
}Tpool[maxn << 2], *Ttail = Tpool, *root;
struct EDGE {
int to;
EDGE *nxt;
EDGE(int to = 0, EDGE *nxt = NULL): to(to), nxt(nxt) {}
}Epool[maxn << 2], *Etail = Epool;
EDGE *head[maxn];
int f[maxn][26], dfn[maxn], dep[maxn], cnt, n, m, redfn[maxn], siz[maxn];
void rot(node *x) {
node *y = x->fa, *z = y->fa;
bool k = x->isr(); node *w = x->ch[!k];
if(y->ntr()) z->ch[y->isr()] = x;
(x->ch[!k] = y)->ch[k] = w;
(y->fa = x)->fa = z;
if(w) w->fa = y;
}
void splay(node *o) {
while(o->ntr()) {
if(o->fa->ntr()) rot(o->isr() ^ o->fa->isr()? o : o->fa);
rot(o);
}
}
void add(int from, int to) {
head[from] = new(Etail++) EDGE(to, head[from]);
}
void dfs(int x, int fa) {
dep[redfn[dfn[x] = ++cnt] = x] = dep[(pool[x].fa = pool + (f[x][0] = fa)) - pool] + (siz[x] = 1);
for(EDGE *i = head[x]; i; i = i->nxt) {
if(i->to == fa) continue;
dfs(i->to, x);
siz[x] += siz[i->to];
}
}
void build(Tree *&o, int l, int r) {
o = new(Ttail++) Tree(l, r, 0, 0);
if(l == r) return(void)(o->max = dep[redfn[l]]);
int mid = (l + r) >> 1;
build(o->ch[0], l, mid), build(o->ch[1], mid + 1, r);
o->upd();
}
void lazy(Tree *o, int l, int r, int k) {
if(l <= o->l && o->r <= r) return (void)(o->trn(k));
o->dwn();
int mid = (o->l + o->r) >> 1;
if(l <= mid) lazy(o->ch[0], l, r, k);
if(r > mid) lazy(o->ch[1], l, r, k);
o->upd();
}
int query(Tree *o, int l, int r) {
if(l <= o->l && o->r <= r) return o->max;
int max = 0;
o->dwn();
int mid = (o->l + o->r) >> 1;
if(l <= mid) max = std::max(max, query(o->ch[0], l, r));
if(r > mid) max = std::max(max, query(o->ch[1], l, r));
return max;
}
node *findroot(node *x) {
while(x->ch[0]) x = x->ch[0];
return x;
}
void access(node *x) {
node *v;
for(node *y = NULL; x; x = (y = x)->fa) {
splay(x);
if(x->ch[1]) v = findroot(x->ch[1]), lazy(root, dfn[v - pool], dfn[v - pool] + siz[v - pool] - 1, 1);
if((x->ch[1] = y)) v = findroot(y), lazy(root, dfn[v - pool], dfn[v - pool] + siz[v - pool] - 1, -1);
}
}
int LCA(int x, int y) {
if(dep[x] < dep[y]) std::swap(x, y);
for(int i = 17; i >= 0; i--) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
if(x == y) return x;
for(int i = 17; i >= 0; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int main() {
n = in(), m = in();
int p, x, y;
for(int i = 1; i < n; i++) x = in(), y = in(), add(x, y), add(y, x);
dfs(1, 0), build(root, 1, n), pool[1].fa = NULL;
for(int j = 1; j <= 17; j++)
for(int i = 1; i <= n; i++)
f[i][j] = f[f[i][j - 1]][j - 1];
while(m --> 0) {
p = in();
if(p == 1) access(pool + in());
if(p == 2) {
x = in(), y = in();
int lca = LCA(x, y);
printf("%d\n", query(root, dfn[x], dfn[x]) + query(root, dfn[y], dfn[y]) - 2 * query(root, dfn[lca], dfn[lca]) + 1);
}
if(p == 3) x = in(), printf("%d\n", query(root, dfn[x], dfn[x] + siz[x] - 1));
}
return 0;
}
上一篇:把spring-boot项目部署到tomcat容器中


下一篇:awk 筛选特定长度的序列