题目背景
题目摘自 WC 模拟试题 (by Philipsweng), 数据自测, 如有问题欢迎反馈
题目描述
在一个偏远的小镇上, 有一些落后的山村. 山村之间通过一些道路来连接. 当然有的山村可能不连通.
一年当中会发生很多大事, 比如说有人提议要在山村 ii 与 jj 之间修建一条道路, 也有人觉得山村 ii 和 jj 之间的道路需要被拆掉.
由于小镇的落后, 镇长不会允许存在两个山村 i,ji,j, 他们存在超过一条路径到达对方. 也就是说, 假如在修建山村 i,ji,j 之间的道路之前, 它们已经连通了, 那么这条道路就不会被修建.
但拆除道路就不一样了. 假如有人建议拆除连接 i,ji,j 的道路, 并且 i,ji,j 的确有道路相连的话, 镇长就会把它拆掉.
除了道路的修建与拆迁外, 热情的山村人也会到处拜访其他人. 有的时候来自山村 ii 的人会想到山村 jj 玩.
但山村人都是不识路的, 那怎么办? 他们有一种奇怪的遍历方式.
设一次旅行的起点为 S, 终点为 T, 点 u 的边集为 V(i), 那么这个走路过程可以用下面的伪代码来表示.
- function DFS(u)
- if u==T then
- finish search
- flag[u]<-true
- random shuffle the vertices order in V(u)
- //here all permutations have equal probability to be chosen
- for i in V(u) do
- if flag[i]==false then
- count++;
- DFS(i);
- count++;
最后 count 就是这次旅行所花时间.
很显然对于一次旅行, count 可能有多种取值, 那么对于这次旅行时间的评估, 就是 count 的期望.
对于每次旅行, 你都要告诉山村人他这次旅行时间的评估是多少.
一开始所有的山村之间都是没有道路连接的.
update: 伪代码好难看, 来个 cpp......
- int count=0;
- void dfs(int u)
- {
- if(u==T)cout<<count,exit(0);
- flag[u]=true;
- random_shuffle(V[u],V[u]+len[u]);
- for(i=0;i<len[u];++i)
- if(!flag[V[i]])count++,dfs(V[i]);
- count++;
- }
输入输出格式
输入格式:
第一行两个整数 N,QN,Q, 表示小镇上总共有 NN 个山村, 一年中发生了 QQ 件大事.
接下来 QQ 行, 每行包括三个整数 type,u,vtype,u,v.
若
- type=0
- t
- y
- p
- e
- =
0, 表示有人建议在
u,v
u,v 之间修建一条道路.
若
- type=1
- t
- y
- p
- e
- =
1, 表示有人建议拆除
u,v
u,v 之间的道路.
若
- type=2
- t
- y
- p
- e
- =
2, 表示山村人要进行一次
u
u 出发到
v
v 结束的旅行.
输出格式:
输出共 Q 行.
对于第 i 件大事, 若 type=0type=0 或 11, 假如这件大事能完成, 则输出 OK, 否则输出 ILLEGAL. 若 type=2type=2, 假如这次旅行能到达终点, 则输出对应的时间评估, 否则输出 ILLEGAL.
对于每个时间评估, 输出保留 4 位小数.
输入输出样例
输入样例 #1: 复制
- 4 9
- 0 1 2
- 0 2 4
- 0 4 1
- 2 1 4
- 0 2 3
- 2 1 4
- 1 4 1
- 1 3 2
- 2 1 3
输出样例 #1: 复制
- OK
- OK
- ILLEGAL
- 2.0000
- OK
- 3.0000
- ILLEGAL
- OK
- ILLEGAL
说明
对于 100\%100% 的数据, N≤100000,Q≤300000,1≤u,v≤NN≤100000,Q≤300000,1≤u,v≤N
本题是 lct 求期望, 有结论是 x 到 y 的期望就是 x 到 y 之间点的个数减一, 所以我们只要用 lct 维护子树信息就可以 (原树和虚子树)
- #include<bits/stdc++.h>
- using namespace std;
- #define re register
- #define R re int
- #define rep(i,a,b) for(R i=a;i<=b;i++)
- #define Rep(i,a,b) for(R i=a;i>=b;i--)
- #define ms(i,a) memset(a,i,sizeof(a))
- #define lc ch[x][0]
- #define rc ch[x][1]
- #define pa fa[x]
- #define I inline int
- template<class T>I read(T &x){
- x=0; char c=0;
- while (!isdigit(c)) c=getchar();
- while (isdigit(c)) x=x*10+(c^48),c=getchar();
- }
- int const N=100001;
- int const M=300001;
- int st[N],top,n,m;
- struct Lct{
- int ch[N][2],r[N],fa[N],s[N],si[N];
- I get(int x){return ch[pa][1]==x;}
- I isr(int x){return ch[pa][0]!=x && ch[pa][1]!=x;}
- I update(int x){s[x]=s[lc]+s[rc]+si[x]+1;}
- I con(int x,int y,int z){fa[x]=y; ch[y][z]=x;}
- I rotate(int x){
- int f=fa[x],g=fa[f],c=get(x),cc=get(f);
- if(!isr(f)) ch[g][cc]=x; fa[x]=g;
- con(ch[x][c^1],f,c); con(f,x,c^1);
- update(f); update(x);
- }
- I pushd(int x){
- if(!r[x]) return 0;
- swap(ch[lc][0],ch[lc][1]); swap(ch[rc][0],ch[rc][1]);
- r[lc]^=1; r[rc]^=1; r[x]=0;
- }
- I splay(int x){
- top=0; int k=x; while (!isr(k)) st[++top]=k,k=fa[k]; ; st[++top]=k;
- while (top) pushd(st[top--]);
- for ( ; !isr(x); rotate(x)){
- if(!isr(pa)) rotate(get(x)==get(pa)? pa:x);
- }
- }
- I access(int x){
- for(int y=0;x;y=x,x=pa){
- splay(x);
- si[x]+=s[rc];
- si[x]-=s[rc=y];
- update(x);
- }
- }
- I make(int x){ access(x); splay(x);r[x]^=1; swap(lc,rc);}
- I find(int x){access(x);splay(x);while (lc) pushd(x),x=lc; return x;}
- I split(int x,int y){make(x); access(y);splay(y);}
- I cut(int x,int y){
- make(x);
- if(find(y)==x && fa[x]==y && !rc){
- fa[x]=ch[y][0]=0; update(y);return 1;
- }else return 0;
- }
- I link(int x,int y){
- make(x);
- if(find(y)==x) return 0;
- si[fa[x]=y]+=s[x]; update(y);
- return 1;
- }
- }lct;
- int main(){
- read(n); read(m);
- rep(i,1,n) lct.s[i]=1;
- while (m--){
- int x,y,z; read(z); read(x); read(y);
- if(z==0) {
- if(lct.link(x,y)) puts("OK");
- else puts("ILLEGAL");
- int t=lct.find(x);
- }
- if(z==1){
- if(lct.cut(x,y)) puts("OK");
- else puts("ILLEGAL");
- }
- if(z==2){
- if(lct.find(x)!=lct.find(y)) puts("ILLEGAL");
- else {
- lct.split(x,y);
- printf("%d.0000\n",lct.s[y]-lct.si[y]-1);
- }
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2899987.html