正文

bzoj-3779重组病毒linkcuttree+线段树+dfs序

DaD3zZ  DaD3zZ  2022-08-19  672

关键词：

3779: 重组病毒

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 224 Solved: 95
[Submit][Status][Discuss]

Description

黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播，某安全机构策划了一次实验，来研究这种病毒。
实验在一个封闭的局域网内进行。局域网内有n台计算机，编号为1~n。一些计算机之间通过网线直接相连，形成树形的结构。局域网中有一台特殊的计算机，称之为核心计算机。根据一些初步的研究，研究员们拟定了一个一共m步的实验。实验开始之前，核心计算机的编号为1，每台计算机中都有病毒的一个变种，而且每台计算机中的变种都不相同。实验中的每一步会是下面中的一种操作：

1、 RELEASE x
在编号为x的计算机中植入病毒的一个新变种。这个变种在植入之前不存在于局域网中。

2、 RECENTER x
将核心计算机改为编号为x的计算机。但是这个操作会导致原来核心计算机中的病毒产生新变种，并感染过来。换言之，假设操作前的核心计算机编号为y，相当于在操作后附加了一次RELEASE y的操作。
根据研究的结论，在植入一个新变种时，病毒会在局域网中搜索核心计算机的位置，并沿着网络中最短的路径感染过去。
而第一轮实验揭露了一个惊人的真相：病毒的不同变种是互斥的。新变种在感染一台已经被旧变种感染的电脑时，会把旧变种完全销毁之后再感染。但研究员发现了实现过程中的漏洞。如果新变种在感染过程中尚未销毁过这类旧变种，需要先花费1单位时间分析旧变种，才能销毁。如果之前销毁过这类旧变种，就可以认为销毁不花费时间。病毒在两台计算机之间的传播亦可认为不花费时间。

研究员对整个感染过程的耗时特别感兴趣，因为这是消灭病毒的最好时机。于是在m步实验之中，研究员有时还会做出如下的询问：
3、 REQUEST x
询问如果在编号为x的计算机的关键集合中的计算机中植入一个新变种，平均感染时间为多长。编号为y的计算机在编号为x的计算机的关键集合中，当且仅当从y沿网络中的最短路径感染到核心计算机必须经过x。由于有RECENTER操作的存在，这个集合并不一定是始终不变的。

至此，安全机构认为已经不需要实际的实验了，于是他们拜托你编写一个程序，模拟实验的结果，并回答所有的询问。

Input

输入的第一行包含两个整数n和m，分别代表局域网中计算机的数量，以及操作和询问的总数。
接下来n-1行，每行包含两个整数x和y，表示局域网中编号为x和y的计算机之间有网线直接相连。
接下来m行，每行包含一个操作或者询问，格式如问题描述中所述。

Output

对于每个询问，输出一个实数，代表平均感染时间。输出与答案的绝对误差不超过 10^(-6)时才会被视为正确。

Sample Input

8 6
1 2
1 3
2 8
3 4
3 5
3 6
4 7
REQUEST 7
RELEASE 3
REQUEST 3
RECENTER 5
RELEASE 2
REQUEST 1

Sample Output

4.0000000000
2.0000000000
1.3333333333

HINT

N < = 1 00 000 M < = 1 00 000

Source

Solution

这道题真是容易写残调半天。

把题目转化一下发现这些过程实际上类似于LinkCutTree，具体的三个操作分别是：

1、将x到根路径上的所有点染成一种新的颜色；
2、将x到根路径上的所有点染成一种新的颜色，并且把这个点设为根；
3、查询以x为根的子树中所有点到根虚边数+1 的平均值。

然后1对应Access，2对应makeroot，3维护子树和。

LinkCutTree并不支持维护子树和，所以用dfs序+线段树维护，在每次Access的时候会对相应节点子树+1-1，这个用线段树很好实现。

然后至于换根对线段树的影响，就一如既往的讨论三种情况即可。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define LL long long
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
}
#define MAXN 100010
int N,M;
struct EdgeNode{int next,to,from;}edge[MAXN<<1];
int head[MAXN],cnt=1;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].from=u;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int pl[MAXN],dfn,pre[MAXN],pr[MAXN],root,father[17][MAXN],deep[MAXN];
LL val[MAXN];
inline void DFS(int now,int last)
{
    pl[now]=++dfn; pre[dfn]=now; val[now]=val[last]+1;
    for (int i=1; i<=16; i++)
        if (deep[now]>=(1<<i)) father[i][now]=father[i-1][father[i-1][now]];
            else break;
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            father[0][edge[i].to]=now,
            deep[edge[i].to]=deep[now]+1,
            DFS(edge[i].to,now);
    pr[now]=dfn;
}
inline int LCA(int x,int y)
{
    if (deep[x]<deep[y]) swap(x,y);
    int dd=deep[x]-deep[y];
    for (int i=0; i<=16; i++) if (dd&(1<<i)) x=father[i][x];
    for (int i=16; i>=0; i--)
        if (father[i][x]!=father[i][y])
            x=father[i][x],y=father[i][y];
    return x==y? x:father[0][x];
}
inline int Jump(int x,int k)
{
    for (int i=0; i<=16; i++)
        if (k&(1<<i)) x=father[i][x];
    return x;
}
namespace SgtTree
{
    LL tree[MAXN<<2],tag[MAXN<<2]; int size[MAXN<<2];
    inline void Update(int now) {tree[now]=tree[now<<1]+tree[now<<1|1];}
    inline void Add(int now,LL val) {tree[now]+=(LL)size[now]*val; tag[now]+=val;}
    inline void PushDown(int now)
    {
        if (!tag[now] || size[now]==1) return;
        Add(now<<1,tag[now]); Add(now<<1|1,tag[now]);
        tag[now]=0;
    }
    inline void Build(int now,int l,int r)
    {
        size[now]=r-l+1;
        if (l==r) {tree[now]=val[pre[l]]; return;}
        int mid=(l+r)>>1;
        Build(now<<1,l,mid); Build(now<<1|1,mid+1,r);
        Update(now);
    }
    inline void Modify(int now,int l,int r,int L,int R,LL val)
    {
        if (L>R) return;
        PushDown(now);
        if (L<=l && R>=r) {Add(now,val); return;}
        int mid=(l+r)>>1;
        if (L<=mid) Modify(now<<1,l,mid,L,R,val);
        if (R>mid) Modify(now<<1|1,mid+1,r,L,R,val);
        Update(now);
    }
    inline LL QueryT(int now,int l,int r,int L,int R)
    {
        if (L>R) return 0;
        PushDown(now);
        if (L<=l && R>=r) return tree[now];
        int mid=(l+r)>>1; LL re=0;
        if (L<=mid) re+=QueryT(now<<1,l,mid,L,R);
        if (R>mid) re+=QueryT(now<<1|1,mid+1,r,L,R);
        return re;
    }
    inline int QueryS(int now,int l,int r,int L,int R)
    {
        if (L>R) return 0;
        PushDown(now);
        if (L<=l && R>=r) return size[now];
        int mid=(l+r)>>1,re=0;
        if (L<=mid) re+=QueryS(now<<1,l,mid,L,R);
        if (R>mid) re+=QueryS(now<<1|1,mid+1,r,L,R);
        return re;
    }
    inline double Query(int now)
    {
        if (!now) return 0;
        LL sum=0; int x,y,sz=0;
        if (now==root)
            sz=QueryS(1,1,N,pl[1],pr[1]),sum=QueryT(1,1,N,pl[1],pr[1]);
        else
            {
                x=LCA(root,now);
                if (x!=now)
                    sz=QueryS(1,1,N,pl[now],pr[now]),sum=QueryT(1,1,N,pl[now],pr[now]);
                else
                    y=Jump(root,deep[root]-deep[now]-1),
                    sz=QueryS(1,1,N,1,pl[y]-1)+QueryS(1,1,N,pr[y]+1,N),
                    sum=QueryT(1,1,N,1,pl[y]-1)+QueryT(1,1,N,pr[y]+1,N);
            }
        return 1.0*sum/sz;
    }
    inline void Modify(int now,LL val)
    {
        if (!now) return;
        int x,y;
        if (now==root) Modify(1,1,N,pl[1],pr[1],val);
        else
            {
                x=LCA(root,now);
                if (x!=now)
                    Modify(1,1,N,pl[now],pr[now],val);
                 else 
                    y=Jump(root,deep[root]-deep[now]-1),
                    Modify(1,1,N,1,pl[y]-1,val),Modify(1,1,N,pr[y]+1,N,val);
            }
    }
}using namespace SgtTree;
namespace LCT
{
    int fa[MAXN],son[MAXN][2],left[MAXN],right[MAXN]; bool rev[MAXN];
    inline bool is_root(int x) {return !fa[x] || son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}
    inline void Pushup(int x)
    {
        if (!x) return;
        left[x]=right[x]=x;
        if (son[x][0]) left[x]=left[son[x][0]];
        if (son[x][1]) right[x]=right[son[x][1]];
    }
       inline void Rev(int x) {if (!x) return; swap(left[x],right[x]),swap(son[x][0],son[x][1]),rev[x]^=1;}
    inline void Pushdown(int x) {if (!x) return; if (rev[x]) Rev(son[x][0]),Rev(son[x][1]),rev[x]^=1;}
    inline void Rotate(int x)
    {
        int y=fa[x],w=son[y][1]==x,z=fa[y];
        son[y][w]=son[x][w^1];
        if (son[x][w^1]) fa[son[x][w^1]]=y;
        if (son[z][0]==y) son[z][0]=x; else if (son[z][1]==y) son[z][1]=x;
        fa[x]=z; fa[y]=x; son[x][w^1]=y; Pushup(y);
    }
    int stack[MAXN];
    inline void Splay(int x)
    {
        int t=x,top=0,y; stack[++top]=x;
        while (!is_root(t)) stack[++top]=t=fa[t];
        while (top) Pushdown(stack[top--]);
        while (!is_root(x))
            {
                y=fa[x];
                if (!is_root(y))
                    if ((son[fa[y]][0]==y)^(son[y][0]==x)) Rotate(x);
                        else Rotate(y);
                Rotate(x);
            }
        Pushup(x);
    }
    inline void Access(int x)
    {
        for (int y=0; x; y=x,x=fa[x])
            Splay(x),
            SgtTree::Modify(left[y],-1),
            SgtTree::Modify(left[son[x][1]],1),
            son[x][1]=y,Pushup(x);
    }
    inline void Makeroot(int x) {Access(x); Splay(x); Rev(x);}
}using namespace LCT;
int main()
{
    N=read(),M=read();
    for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);
    DFS(root=1,0);
    SgtTree::Build(1,1,N);
    for (int i=1; i<=N; i++) LCT::fa[i]=father[0][i],LCT::left[i]=LCT::right[i]=i;
    while (M--)
        {
            char opt[10]; int x;
            scanf("%s",opt+1); x=read();
            switch (opt[3])
                {
                    case ‘L‘: LCT::Access(x); break;
                    case ‘C‘: LCT::Makeroot(x); root=x; break;
                    case ‘Q‘: printf("%.10lf
",SgtTree::Query(x)); break;
                }
        }
    return 0;
}

突然想起char哥说这种题做的非常爽...然而，我因为线段树区间操作手贱达成了if (l==r)外加LCT中忘swap了一个地方两个脑残错误调了整整两节晚自习啊，感觉非常蛋疼；

这说明以后写数据结构，思路一定要清晰，写的时候一定不能图快，要不然Debug浪费的时间更多。

外加，自己常数怎么这么大啊，BZOJ成功倒数rank1......

bzoj3779重组病毒lct+线段树（维护dfs序）(代码片段)

...iption黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播，某安全机构策划了一次实验，来研究这种病毒。实验在一个封闭的局域... 查看详情

bzoj3779重组病毒lct+树上倍增+dfs序+树状数组区间修改区间查询

题目描述给出一棵n个节点的树，每一个节点开始有一个互不相同的颜色，初始根节点为1。定义一次感染为：将指定的一个节点到根的链上的所有节点染成一种新的颜色，代价为这条链上不同颜色的数目。现有m次操作，每次为一... 查看详情

bzoj3779重组病毒——lct维护子树信息(代码片段)

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3779调了很久……已经懒得写题解了。https://www.cnblogs.com/Zinn/p/10124183.html线段树和LCT是分开的。线段树的子树一直是相对于1号点而言。线段树上维护的值总是相对于当前的rt的。怎么保... 查看详情

bzoj3779重组病毒——lct+树状数组(区间修改+区间查询)(代码片段)

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3779RELEASE操作可以对应LCT的access，RECENTER则是makeroot；考虑颜色数，把一条实边变成虚边，子树+1，虚变实子树-1；但有换根操作，怎么维护子树？也可以用dfs序线段树维护，其实换rt只... 查看详情

bzoj3779lct线段树dfs序坑

hhhh抄了半天lty代码最后T了对拍也没事..药丸mine#pragmaGCCoptimize("O3")//BySiriusRen#include<bits/stdc++.h>usingnamespacestd;constintN=100500;typedeflonglongll;intn,m,xx,yy,first[N],next[N*2],v[N*2],tot;in 查看详情

linkcuttree学习笔记

从这里开始动态树问题和LinkCutTree一些定义access操作换根操作link和cut操作时间复杂度证明LinkCutTree维护链上信息LinkCutTree维护子树信息小结动态树问题和LinkCutTree　　动态树问题是一类要求维护一个有根树森林，支持对树的分割,... 查看详情

3779:重组病毒(代码片段)

传送门一道很有奥妙的题．发现修改操作和access有着不可不说的关系．因为操作的特殊性，每种颜色在树上是一段连续的区间．不会被切开．若x跟父亲颜色相同，设x到父亲的边的权值为0，否则为1那么一个点到根的颜色就是它... 查看详情

linkcuttree入门

鉴于最近写bzoj还有51nod都出现写不动的现象，决定学习一波厉害的算法/数据结构。linkcuttree：研究popoqqq那个神ppt。bzoj1036：维护access操作就可以了。#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#include<q 查看详情

数据结构专题-学习笔记：linkcuttree动态树

1.前言LinkCutTree动态树，简称LCT，是一种维护动态森林的数据结构。前置知识：Splay。2.LCT例题：P3690【模板】动态树（LinkCutTree）2.1实链剖分实链剖分也是一种对树的剖分方式，类似于重链剖分和长链剖分，其将一棵树上的边，随... 查看详情

sdoi2017round1day1题解（bzoj4816bzoj4817bzoj4818）

不知道有几个AK的，除了出题人SB搬了个BZOJ3779以外，应该没什么因素阻碍AK吧。要是SCOI考这套题多好。BZOJ4816数字表格SB反演，推出$ans=prod_{i=1}^nf^{sum_{j=1}^{leftlfloorfracni ight floor}mu(j)leftlfloorfracn{ij} ight floorleftlfloorfrac 查看详情

ac日记——模板linkcuttree洛谷p3690

【模板】LinkCutTree 思路：　　LCT模板；代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn300005intn,m,val[maxn];inttop,ch[maxn][2],f[maxn],xr[maxn],q[maxn],rev[maxn];inlinevoidin(int&now 查看详情

p3690linkcuttree(动态树)

干脆整个LCT模板吧。缺个链上修改和子树操作，链上修改的话join(u,v)然后把vsplay到树根再打个标记就好。至于子树操作...以后有空的话再学(咕咕咕警告)1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=1e5+10;5intn,m,a[N],X... 查看详情

[]linkcuttree

坑了好久，本来打算就这样弃着，最近又被神秘力量驱使来学这个东西，过程很痛苦但最终还是知道它到底是啥了它可以用来对森林进行各种操作，为了快速地实现各种操作，我们要像树剖一样把整个森林剖成许多条链，每条链... 查看详情

luogu3690模板linkcuttree（动态树）

参考there和there#include<iostream>#include<cstdio>usingnamespacestd;intn,m,val[300005],ch[300005][2],sum[300005],fa[300005],uu,vv,opt;intrev[300005];voidpushDown(intx)if(rev[x])swap(ch[x][0 查看详情

luogup3690模板linkcuttree（动态树）

#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>#include<climits>#include<stack>#include<vector>#include<queue& 查看详情

linkcuttree（无图慎入）(代码片段)

类似树链剖分（其实直接记住就可以了），提前放代码1#include<cstdio>2#include<cstdlib>3#include<iostream>4#include<algorithm>5#include<cstring>6#include<climits>7#include<cmath>8#define 查看详情

luogu3690模板linkcuttree（动态树）

题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情

linkcuttree求最小生成树(代码片段)

对边建点，原图中的边转化为点的点-边的点-点的点于是用LCT维护连通关系，并支持查询最大值位置即可#include<bits/stdc++.h>usingnamespacestd;constintN=300005;intn,m,val[N],t1,t2,t3;namespacelct inttop,q[N],ch[N][2],fa[N],rev[N]; intmx[N]; inlin 查看详情