LCT强强！以前总是觉得LCT非常的难懂（当然现在也是的），但实际上它真的是很厉害的一种东西。它是一种动态的链剖分结构，其实就是对于剖分出来的重链使用LCT去进行维护。cut 与 link 两个操作让我们可以构造出希望存在的链（动态更新），而 split 操作则可以提取出任意一条从 \(u\) 到 \(v\) 的链使得这条链成为重链，也就是处于一棵 splay 当中，并用根节点来返回信息。可以说，大部分与链有关的问题都可以考虑使用LCT来求解。

　　那么这道题乍一看1操作十分的棘手，但如果和LCT联想的话会发现实际上这就是一个 access 的操作，让一个节点到根的路径成为重链并断开原有的重儿子。这样一个条路径上的颜色个数，就是经过的虚边的条数。对于操作2，实际上是一个 LCT 的模板应用。我们维护颜色段的信息，用 \(LC[u]\) 和 \(RC[u]\) 分别代表以\(u\) 为根节点在 splay 上的子树的最右和最左两个节点的颜色。这样就可以维护了。修改颜色使用一个标记即可。

　　而3操作我们可以发现：在 access 的时候，我们每修改一条虚边为实边，就会断开一条原本为实边的边为虚边。这样对于它们子树的贡献分别是 \(-1, +1\)。我们在线段树上维护一下加减值即可。不过要注意由于3操作中的 access 已经用于维护树的形态了，我们就不能再随意的去变动它。所以为了实现2和3操作，我们必须使用两棵LCT。以及在翻转子树的时候，\(LC[u]\) 和 \(RC[u]\) 都必须要翻转！

　　这里我也有一个不是很理解的地方。标记一般来说有两种，一种打了标记表示自身及子树还未被修改，另一种则表示自身已经被修改，子树还未被修改。在以往我写的 LCT 中，翻转标记用第一种来维护完全没有问题。可以加入了覆盖的标记之后，只有第2种才是正确的。我也不是很懂为什么……如果有知道的，还请评论 \ 私信我一下好吗QAQ

　　加之以前我一直以为LCT只能维护链信息，但老师说也是可以维护子树信息的，只要在添加虚边的时候更新一下即可，但这个必须要子树贡献满足可加性才行。

#include <bits/stdc++.h>

using namespace std;

#define maxn 1000000

int n, m, timer, size[maxn];

int id[maxn], dfn[maxn], dep[maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

struct edge

{

    int cnp, to[maxn], last[maxn], head[maxn];

    edge() { cnp = ; }

    void add(int u, int v)

    {

        to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;

        to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;

    }

}E1;

struct Segament_Tree

{

    int mark[maxn], mx[maxn];

    void Build(int p, int l, int r)

    {

        if(l == r) { mx[p] = dep[id[l]]; return; }

        int mid = (l + r) >> ;

        Build(p << , l, mid), Build(p <<  | , mid + , r);

        mx[p] = max(mx[p << ], mx[p <<  | ]);

    }

    void push_down(int u)

    {

        if(!mark[u]) return;

        mark[u << ] += mark[u];  mark[u <<  | ] += mark[u];

        mx[u << ] += mark[u], mx[u <<  | ] += mark[u];

        mark[u] = ;

    }

    void update(int p, int l, int r, int L, int R, int x)

    {

        if(L <= l && R >= r)

        {

            mark[p] += x; mx[p] += x;

            return;

        }

        if(L > r || R < l) return;

        int mid = (l + r) >> ;

        push_down(p);

        update(p << , l, mid, L, R, x); update(p <<  | , mid + , r, L, R, x);

        mx[p] = max(mx[p << ], mx[p <<  | ]);

    }

    int query(int p, int l, int r, int L, int R)

    {

        if(L <= l && R >= r) return mx[p];

        if(L > r || R < l) return ;

        push_down(p); int mid = (l + r) >> ;

        return max(query(p << , l, mid, L, R), query(p <<  | , mid + , r, L, R));

    }

}ST;

struct Link_Cut_Tree

{

    int fa[maxn], rev[maxn], ch[maxn][];

    int sum[maxn], LC[maxn], RC[maxn], col[maxn];

    int tot, flag, mark[maxn], top[maxn]; 

    bool is_root(int u) { return (ch[fa[u]][] != u) && ( ch[fa[u]][] != u ); }

    void Modify(int u, int x) { if(!u) return; mark[u] = x; LC[u] = RC[u] = col[u] = x, sum[u] = ; }

    void Rev(int u) { if(!u) return; rev[u] ^= ; swap(ch[u][], ch[u][]); swap(LC[u], RC[u]); }

    void push_down(int u)

    {

        if(!is_root(u)) push_down(fa[u]);

        if(rev[u]) Rev(ch[u][]), Rev(ch[u][]), rev[u] = ;

        if(mark[u]) Modify(ch[u][], mark[u]), Modify(ch[u][], mark[u]), mark[u] = ;

    }

    void update(int u)

    {

        int lc = ch[u][], rc = ch[u][];

        if(flag)

        {

            sum[u] = sum[lc] + sum[rc]  + ((col[u] != RC[lc]) && (col[u] != LC[rc]));

            sum[u] -= ((col[u] == RC[lc]) && (col[u] == LC[rc]));

            LC[u] = LC[lc], RC[u] = RC[rc];

            if(!lc) LC[u] = col[u]; if(!rc) RC[u] = col[u];

        }

        else top[u] = top[lc] ? top[lc] : u;

    }

    void rotate(int u)

    {

        int f = fa[u], gf = fa[f];

        int k = ch[f][] == u;

        fa[u] = gf; if(!is_root(f)) ch[gf][ch[gf][] == f] = u;

        ch[f][k] = ch[u][k ^ ], fa[ch[u][k ^ ]] = f;

        fa[f] = u, ch[u][k ^ ] = f;

        update(f), update(u);

    }

    void Splay(int u)

    {

        push_down(u);

        while(!is_root(u))

        {

            int f = fa[u], gf = fa[f];

            if(!is_root(f)) (ch[gf][] == f) ^ (ch[f][] == u) ? rotate(u) : rotate(f);

            rotate(u);

        }

        update(u);

    }

    void Access(int u)

    {

        for(int i = u, last = ; i; last = i, i = fa[i])

        {

            Splay(i);

            if(!flag)

            {

                int x = top[last], y = top[ch[i][]];

                if(x) ST.update(, , n, dfn[x], dfn[x] + size[x] - , -);

                if(y) ST.update(, , n, dfn[y], dfn[y] + size[y] - , );

            }

            ch[i][] = last; update(i);

        }

    }

    void Make_root(int u) { Access(u); Splay(u); Rev(u); }

    void Split(int u, int v) { Make_root(u); Access(v); Splay(v); }

    void Change1(int u) { ++ tot; Access(u); }

    void Change2(int u) { Split(, u); Modify(u, ++ tot); }

    void Link(int u, int v) { Make_root(u); fa[u] = v; }

    int Query(int u, int v) { Split(u, v); return sum[v]; }

}LCT1, LCT2;

void dfs(int u, int fa)

{

    LCT1.fa[u] = fa;

    dfn[u] = ++ timer; size[u] = ; dep[u] = dep[fa] + ;

    id[timer] = u; LCT1.top[u] = u;

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        if(v == fa) continue;

        dfs(v, u); size[u] += size[v];

    }

}

int main()

{

    n = read(), m = read(); LCT2.flag = ;

    for(int i = ; i <= n; i ++)

        LCT2.col[i] = LCT2.RC[i] = LCT2.LC[i] = ++ LCT2.tot, LCT2.sum[i] = ;

    for(int i = ; i < n; i ++)

    {

        int x = read(), y = read();

        E1.add(x, y); LCT2.Link(x, y);

    }

    dfs(, );

    ST.Build(, , n);

    for(int i = ; i <= m; i ++)

    {

        int opt = read();

        if(opt == )

        {

            int x = read();

            LCT1.Change1(x); LCT2.Change2(x);

        }

        else if(opt == )

        {

            int x = read(), y = read();

            printf("%d\n", LCT2.Query(x, y));

        }

        else if(opt == )

        {

            int x = read();

            printf("%d\n", ST.query(, , n, dfn[x], dfn[x] + size[x] - ));

        }

    }

    return ;

}

最新文章

  1. 按年、季度、月分组&amp;&amp;计算日期和时间的函数
  2. Linux测试环境部署tomcat（二）
  3. 在 2017 年将会更加流行的 6 个 Web 开发趋势
  4. Eclipse中tomcat之后，tomcat的相关配置会被Eclipse重置
  5. 教程-Delphi编译就报毒
  6. HTML注释的一些规范
  7. HTTP-304 NOT Modified
  8. PHP学习之［第04讲］PHP5.4 运算符、流程控制
  9. ASP.NET常用编程代码(一)
  10. POJ 3268 Silver Cow Party （ Dijkstra ）
  11. spring+struts2+ibatis 框架整合以及解析
  12. 如何将数据库中存的树转化为树形列表(以easyui的tree为例)
  13. TestNG entryset的用法及遍历map的用法
  14. c#死锁示例代码
  15. HashMap是如何实现快速存取的
  16. Suffix
  17. 生成网上下载的EF项目对应的数据库
  18. Android24以上拍照代码
  19. mysql count group by统计条数方法
  20. redis启动.停止.重启

热门文章

  1. Java：当前线程运行完毕，再运行后续逻辑
  2. 数据库c3p0配置文件
  3. Kubernetes网络方案的三大类别和六个场景
  4. 一个体验好的Windows 任务栏缩略图开发心得
  5. unity share current game screen
  6. 「国庆训练」Kingdom of Obsession（HDU-5943）
  7. Visual Stdio Code编辑Mark Down
  8. 从零开始的Python学习Episode 3——字符串格式化与for循环
  9. SpringCloud IDEA 教学 (二) Eureka Service
  10. 有关WCSF的几点整理