@bzoj - 4817@ [Sdoi2017]树点涂色

﹏ヽ暗。殇╰゛Y 2023-06-01 13:56 2阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路  
径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：

1 x:把点x到根节点的路径上所有的点染上一种没有用过的新颜色。  
2 x y:求x到y的路径的权值。  
3 x:在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob一共会进行m次操作。

**Input**  
第一行两个数n,m。  
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。  
接下来m行，表示操作，格式见题目描述  
1<=n,m<=100000

**Output**  
每当出现2,3操作，输出一行。  
如果是2操作，输出一个数表示路径的权值  
如果是3操作，输出一个数表示权值的最大值

**Sample Input**  
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  
**Sample Output**  
3  
4  
2  
2

## @solution@ ##

初看会觉得这道题十分难以下手：对于那个什么“把点x到根结点的路径上所有的点染上一种没有用过的新颜色”这个操作完全没有办法。  
但如果仔细思考，外加你数据结构学得非常非常强，可以发现这个其实就是 link-cut-tree 中的 access 操作。

考虑点破了这一点后，我们该如何维护“点到根结点的路径权值（不同颜色段数量）”。  
其实你发现，这个就 = 点到根结点经过的 link-cut-tree 中的轻边数量 + 1。  
我们考虑在每一次 access 的时候，将所有轻边变重边，重边变轻边的地方作修改。而根据 link-cut-tree 的时间复杂度分析这个修改数量均摊 O(logn)。

实现上，我们可以将 “单边修改+到根的链查询” 变为 “子树修改+单点查询”，转为 dfs 序然后线段树维护。  
对于询问 2 就只需要查询出 lca 然后变成 f(u) + f(v) - 2\*f(lca)。  
对于询问 3，将树转为 dfs 序后就在 dfs 序上查询最大值。

时间复杂度 O(nlog^2n），瓶颈卡在操作 1 的 access + 线段树上修改，其他两个询问每一次是 O(logn)。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 100000; int dfn[MAXN + 5], tid[MAXN + 5], siz[MAXN + 5], dep[MAXN + 5], fa[20][MAXN + 5], dcnt = 0; struct Segtree{ struct node{ int l, r; int tg, mx; }t[4*MAXN + 5]; void pushdown(int x) { if( t[x].tg ) { t[x<<1].tg += t[x].tg, t[x<<1].mx += t[x].tg; t[x<<1|1].tg += t[x].tg, t[x<<1|1].mx += t[x].tg; t[x].tg = 0; } } void pushup(int x) { t[x].mx = max(t[x<<1].mx, t[x<<1|1].mx); } void build(int x, int l, int r) { t[x].l = l, t[x].r = r, t[x].tg = 0, t[x].mx = 0; if( l == r ) { t[x].mx = dep[dfn[l]] - 1; return ; } int mid = (l + r) >> 1; build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r); pushup(x); } void modify(int x, int l, int r, int d) { if( l > t[x].r || r < t[x].l ) return ; if( l <= t[x].l && t[x].r <= r ) { t[x].tg += d, t[x].mx += d; return ; } pushdown(x); modify(x << 1, l, r, d); modify(x << 1 | 1, l, r, d); pushup(x); } int query(int x, int l, int r) { if( l > t[x].r || r < t[x].l ) return 0; if( l <= t[x].l && t[x].r <= r ) return t[x].mx; pushdown(x); return max(query(x << 1, l, r), query(x << 1 | 1, l, r)); } }T1; struct Link_Cut_Tree{ struct node{node *ch[2], *fa;}pl[MAXN + 5], *NIL; Link_Cut_Tree() { NIL = &pl[0]; NIL->ch[0] = NIL->ch[1] = NIL->fa = NIL; } bool is_root(node *x) { return x->fa->ch[0] != x && x->fa->ch[1] != x; } void set_child(node *x, node *y, int d) { if( x != NIL ) x->ch[d] = y; if( y != NIL ) y->fa = x; } void rotate(node *x) { node *y = x->fa; int d = (y->ch[1] == x); if( is_root(y) ) x->fa = y->fa; else set_child(y->fa, x, (y->fa->ch[1] == y)); set_child(y, x->ch[!d], d); set_child(x, y, !d); } void splay(node *x) { while( !is_root(x) ) { node *y = x->fa; if( is_root(y) ) rotate(x); else { if( (y->fa->ch[1] == y) == (y->ch[1] == x) ) rotate(y); else rotate(x); rotate(x); } } } node *find(node *x) { node *ret = x; while( ret->ch[0] != NIL ) ret = ret->ch[0]; splay(ret); return ret; } void access(node *x) { node *y = NIL; while( x != NIL ) { splay(x); node *k = x->ch[1]; x->ch[1] = y; if( k != NIL ) { k = find(k); T1.modify(1, tid[k-pl], tid[k-pl]+siz[k-pl]-1, 1); } x = find(x); if( x->fa != NIL ) T1.modify(1, tid[x-pl], tid[x-pl]+siz[x-pl]-1, -1); y = x, x = x->fa; } } }T2; Link_Cut_Tree::node *nd[MAXN + 5]; struct edge{ edge *nxt; int to; }edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0]; void addedge(int u, int v) { edge *p = (++ecnt); p->to = v, p->nxt = adj[u], adj[u] = p; p = (++ecnt); p->to = u, p->nxt = adj[v], adj[v] = p; } void dfs(int x, int f) { dfn[++dcnt] = x, tid[x] = dcnt, dep[x] = dep[f] + 1, siz[x] = 1, fa[0][x] = f; for(int i=1;i<20;i++) fa[i][x] = fa[i-1][fa[i-1][x]]; for(edge *p=adj[x];p;p=p->nxt) { if( p->to == f ) continue; dfs(p->to, x); siz[x] += siz[p->to]; } } int lca(int u, int v) { if( dep[u] < dep[v] ) swap(u, v); for(int i=19;i>=0;i--) if( dep[fa[i][u]] >= dep[v] ) u = fa[i][u]; if( u == v ) return u; for(int i=19;i>=0;i--) if( fa[i][u] != fa[i][v] ) u = fa[i][u], v = fa[i][v]; return fa[0][u]; } int main() { int n, m; scanf("%d%d", &n, &m); for(int i=1;i<n;i++) { int a, b; scanf("%d%d", &a, &b); addedge(a, b); } for(int i=1;i<=n;i++) nd[i] = &T2.pl[i], nd[i]->fa = nd[i]->ch[0] = nd[i]->ch[1] = T2.NIL; dfs(1, 0); for(int i=2;i<=n;i++) nd[i]->fa = nd[fa[0][i]]; T1.build(1, 1, n); for(int i=1;i<=m;i++) { int op; scanf("%d", &op); if( op == 1 ) { int x; scanf("%d", &x); T2.access(nd[x]); } else if( op == 2 ) { int x, y; scanf("%d%d", &x, &y); int l = lca(x, y); printf("%d\n", T1.query(1, tid[x], tid[x]) + T1.query(1, tid[y], tid[y]) - 2*T1.query(1, tid[l], tid[l]) + 1); } else { int x; scanf("%d", &x); printf("%d\n", T1.query(1, tid[x], tid[x]+siz[x]-1) + 1); } } }

## @details@ ##

感觉这个思想还是挺有意思的（虽然最近好像就莫名其妙变成了一种套路？）

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11337623.html