【bzoj 3779】重组病毒

首页 > 代码库 > 【bzoj 3779】重组病毒

2024-10-11 17:01:39 217人阅读

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<=100000 ，M<=100000

调了几个世纪终于调出来了……LCT+dfs序线段树。

令每个点权值为这个点到根的路径上虚边数+1，一开始时都是虚边，点权即为深度。

操作1可以神转换为access。在

（顺便吐槽一句，结构体好丑啊T_T本来以为写结构体会快一些的，其实……仿佛差不多

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=100010;
  6 int n,m,x,y,cnt,dfsn,rt=1;//注意初始化rt为1 
  7 int head[N],st[N];
  8 struct edge{int u,v,next;}e[N*2];//邻接表 
  9 struct leaf{int l,r;long long sum,tag;}t[N*4];//线段树 
 10 struct node{int p,fa,c[2],deep,in,out;bool rev;}tr[N];//splay
 11 int read()
 12 {
 13     int x=0,f=1;char c=getchar();
 14     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
 15     while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
 16     return x*f;
 17 }
 18 void ins(int a,int b){cnt++;e[cnt].u=a;e[cnt].v=b;e[cnt].next=head[a];head[a]=cnt;}
 19 void insert(int a,int b){ins(a,b);ins(b,a);}
 20 void qadd(int num,long long w)
 21 {
 22     t[num].tag+=w;
 23     t[num].sum+=(long long)(t[num].r-t[num].l+1)*w;
 24 }
 25 void pushup(int num){t[num].sum=t[num<<1].sum+t[num<<1|1].sum;}
 26 void pushdown(int num)//线段树下传tag 
 27 {
 28     if(!t[num].tag)return;
 29     qadd(num<<1,t[num].tag);
 30     qadd(num<<1|1,t[num].tag);
 31     t[num].tag=0;
 32 }
 33 bool isroot(int k){return !k||(tr[tr[k].fa].c[0]!=k&&tr[tr[k].fa].c[1]!=k);}
 34 void down(int k)//下传翻转标记 ，注意不要跟pushdown弄混 
 35 {
 36     if(tr[k].rev)
 37     {
 38         int l=tr[k].c[0],r=tr[k].c[1];
 39         tr[k].rev^=1;tr[l].rev^=1;tr[r].rev^=1;
 40         swap(tr[k].c[0],tr[k].c[1]);
 41     }
 42 }
 43 void rotate(int x)
 44 {
 45     int y=tr[x].fa,z=tr[y].fa,l,r;
 46     if(tr[y].c[0]==x)l=0;else l=1;r=l^1;
 47     if(!isroot(y)){if(tr[z].c[0]==y)tr[z].c[0]=x;else tr[z].c[1]=x;}
 48     tr[x].fa=z;tr[y].fa=x;tr[tr[x].c[r]].fa=y;
 49     tr[y].c[l]=tr[x].c[r];tr[x].c[r]=y;
 50 }
 51 void splay(int x)
 52 {
 53     int top=0;st[++top]=x;
 54     for(int i=x;!isroot(i);i=tr[i].fa)st[++top]=tr[i].fa;
 55     for(int i=top;i;i--)down(st[i]);
 56     while(!isroot(x))
 57     {
 58         int y=tr[x].fa,z=tr[y].fa;
 59         if(!isroot(y))
 60         {
 61             if((tr[y].c[0]==x)^(tr[z].c[0]==y))rotate(x);
 62             else rotate(y);
 63         }
 64         rotate(x);
 65     }
 66 }
 67 void build(int num,int l,int r)
 68 {
 69     t[num].l=l;t[num].r=r;
 70     if(l==r)return;
 71     int mid=(l+r)>>1;
 72     build(num<<1,l,mid);build(num<<1|1,mid+1,r);
 73 }
 74 void add(int num,int l,int r,long long w)//线段树区间加 
 75 {
 76     if(l>r)return;
 77     if(l<=t[num].l&&t[num].r<=r){qadd(num,w);return;}
 78     if(t[num].l==t[num].r)return;
 79     pushdown(num);
 80     int mid=(t[num].l+t[num].r)>>1;
 81     if(l<=mid)add(num<<1,l,r,w);
 82     if(r>mid)add(num<<1|1,l,r,w);
 83     pushup(num);
 84 }
 85 void dfs(int now,int last)
 86 {
 87     tr[now].p=tr[now].fa=last;
 88     tr[now].in=++dfsn;
 89     tr[now].deep=tr[last].deep+1;
 90     add(1,tr[now].in,tr[now].in,tr[now].deep);//在线段树中更新 
 91     for(int i=head[now];i;i=e[i].next)
 92         if(e[i].v!=last)dfs(e[i].v,now);//记得判父节点 
 93     tr[now].out=dfsn;
 94 }
 95 long long query(int num,int l,int r)//线段树区间求和 
 96 {
 97     if(l>r)return 0;
 98     if(l<=t[num].l&&t[num].r<=r)return t[num].sum;
 99     pushdown(num);//记得下传tag 
100     long long ans=0;
101     int mid=(t[num].l+t[num].r)>>1;
102     if(l<=mid)ans+=query(num<<1,l,r);
103     if(r>mid)ans+=query(num<<1|1,l,r);
104     return ans;
105 }
106 int find(int num,int goal)//查找goal在num的哪一棵子树内 
107 {
108     for(int i=head[num];i;i=e[i].next)
109         if(e[i].v!=tr[num].p&&tr[goal].in>=tr[e[i].v].in&&tr[goal].out<=tr[e[i].v].out)return e[i].v;
110     return 0;
111 }
112 double ask(int num)//REQUEST
113 {
114     if(num==rt)return (double)query(1,1,n)/n;
115     if(tr[rt].in>=tr[num].in&&tr[rt].out<=tr[num].out)//如果rt在num的子树内；这里的子树是相对于原树而言 
116     {
117         int r=find(num,rt);
118         return (double)(query(1,1,tr[r].in-1)+query(1,tr[r].out+1,n))/(n-(tr[r].out-tr[r].in+1));
119     }
120     return (double)query(1,tr[num].in,tr[num].out)/(tr[num].out-tr[num].in+1);
121 }
122 int top(int num)
123 {
124     down(num);
125     while(tr[num].c[0])num=tr[num].c[0],down(num);
126     return num;
127 }
128 void ladd(int num,int w)//子树整体权值加减 
129 {
130     if(num==rt)add(1,1,n,w);
131     else if(tr[rt].in>=tr[num].in&&tr[rt].out<=tr[num].out)
132     {
133         int r=find(num,rt);
134         add(1,1,tr[r].in-1,w);
135         add(1,tr[r].out+1,n,w);
136     }
137     else add(1,tr[num].in,tr[num].out,w);
138 }
139 void acs(int num)
140 {
141     int r=0;
142     while(num)
143     {
144         splay(num);
145         if(tr[num].c[1])ladd(top(tr[num].c[1]),1);
146         if(r)ladd(top(r),-1);
147         tr[num].c[1]=r;r=num;num=tr[num].fa;
148     }
149 }
150 void mrt(int num){splay(num);rt=num;tr[num].rev^=1;}//据题意，换根前已经access过了 
151 int main()
152 {
153     char ch[15];
154     n=read();m=read();
155     for(int i=1;i<n;i++)x=read(),y=read(),insert(x,y);
156     build(1,1,n);dfs(1,0);
157     while(m--)
158     {
159         scanf("%s",ch);x=read();
160         if(ch[2]==‘Q‘)printf("%.10lf\n",ask(x));
161         else
162         {
163             acs(x);
164             if(ch[2]==‘C‘)mrt(x);
165         }
166     }
167     return 0;
168 }

View Code

【bzoj 3779】重组病毒

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【bzoj 3779】重组病毒