\(\color{#0066ff}{ 题目描述 }\)
在一个偏远的小镇上，有一些落后的山村。山村之间通过一些道路来连接。当然有的山村可能不连通。
一年当中会发生很多大事，比如说有人提议要在山村\(i\)与\(j\)之间修建一条道路，也有人觉得山村\(i\)和\(j\)之间的道路需要被拆掉。
由于小镇的落后，镇长不会允许存在两个山村\(i,j\)，他们存在超过一条路径到达对方。也就是说，假如在修建山村\(i,j\)之间的道路之前，它们已经连通了，那么这条道路就不会被修建。
但拆除道路就不一样了。假如有人建议拆除连接\(i,j\)的道路，并且\(i,j\)的确有道路相连的话，镇长就会把它拆掉。
除了道路的修建与拆迁外，热情的山村人也会到处拜访其他人。有的时候来自山村\(i\)的人会想到山村\(j\)玩。
但山村人都是不识路的，那怎么办？他们有一种奇怪的遍历方式。
设一次旅行的起点为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++;
}
\(\color{#0066ff}{输入格式}\)
第一行两个整数\(N,Q\)，表示小镇上总共有\(N\)个山村，一年中发生了\(Q\)件大事。
接下来\(Q\)行，每行包括三个整数\(type,u,v\)。
- 若\(type=0\)，表示有人建议在\(u,v\)之间修建一条道路。
- 若\(type=1\)，表示有人建议拆除\(u,v\)之间的道路。
- 若\(type=2\)，表示山村人要进行一次\(u\)出发到\(v\)结束的旅行。
\(\color{#0066ff}{输出格式}\)
输出共Q行。
对于第i件大事，若\(type=0\)或\(1\)，假如这件大事能完成，则输出OK，否则输出ILLEGAL。若\(type=2\)，假如这次旅行能到达终点，则输出对应的时间评估，否则输出ILLEGAL。
对于每个时间评估，输出保留4位小数。
\(\color{#0066ff}{输入样例}\)
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
\(\color{#0066ff}{输出样例}\)
OK
OK
ILLEGAL
2.0000
OK
3.0000
ILLEGAL
OK
ILLEGAL
\(\color{#0066ff}{数据范围与提示}\)
对于\(100\%\)的数据，\(N≤100000,Q≤300000,1≤u,v≤N\)
\(\color{#0066ff}{ 题解 }\)
这些人走的方式比较nb
简单来说，对于一条路径\(s\to t\)
↑图片来自FlashHu
如果进了某棵子树，那么一定会走完，代价就是进去再回来的总步数
我们设在当前点走正确方向的概率为p
那么答案为\(\begin{aligned}\sum_{i=1}^n2ps_i+\sum_{i=1}^m\sum_{j=1}^n2pa_{ij}\end{aligned}\)
现在考虑p是啥
因为边的生成方式是排列，对于一个排列，有且仅有一个排列与其相反，如果有一个排列使得某条边在另一条边前面，那么必定存在一个排列使得在后面，因此概率\(p=\frac 1 2\)
于是。。。TM答案是整数啊
我们用LCT维护子树，一个是虚子树，一个是总共的
发现答案中是没有t的子树什么事的
所以最后让T到最上面，用T的tot减去T的虚子树部分再减去1（自己）即可
应该是有不合法数据吧。。。在cut的时候如果不判断x是否有右孩子会WA
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 1e5 + 10;
struct LCT {
protected:
struct node {
node *ch[2], *fa;
int tot, siz, rev;
node(int tot = 1, int siz = 0, int rev = 0)
: tot(tot), siz(siz), rev(rev) { ch[0] = ch[1] = fa = NULL; }
void trn() { std::swap(ch[0], ch[1]), rev ^= 1; }
void upd() {
tot = siz + 1;
if(ch[0]) tot += ch[0]->tot;
if(ch[1]) tot += ch[1]->tot;
}
void dwn() {
if(!rev) return;
if(ch[0]) ch[0]->trn();
if(ch[1]) ch[1]->trn();
rev = 0;
}
bool ntr() { return fa && (fa->ch[0] == this || fa->ch[1] == this); }
bool isr() { return this == fa->ch[1]; }
}pool[maxn];
void rot(node *x) {
node *y = x->fa, *z = y->fa;
bool k = x->isr(); node *w = x->ch[!k];
if(y->ntr()) z->ch[y->isr()] = x;
(x->ch[!k] = y)->ch[k] = w;
(y->fa = x)->fa = z;
if(w) w->fa = y;
y->upd(), x->upd();
}
void splay(node *o) {
static node *st[maxn];
int top;
st[top = 1] = o;
while(st[top]->ntr()) st[top + 1] = st[top]->fa, top++;
while(top) st[top--]->dwn();
while(o->ntr()) {
if(o->fa->ntr()) rot(o->isr() ^ o->fa->isr()? o : o->fa);
rot(o);
}
}
void access(node *x) {
for(node *y = NULL; x; x = (y = x)->fa) {
splay(x);
if(x->ch[1]) x->siz += x->ch[1]->tot;
x->ch[1] = y;
if(y) x->siz -= y->tot;
x->upd();
}
}
void makeroot(node *o) { access(o), splay(o), o->trn(); }
node *findroot(node *o) {
access(o), splay(o);
while(o->dwn(), o->ch[0]) o = o->ch[0];
return o;
}
public:
bool link(int l, int r) {
node *x = pool + l, *y = pool + r;
if(findroot(y) == findroot(x)) return false;
makeroot(x), access(y), splay(y);
(x->fa = y)->siz += x->tot;
y->upd();
return true;
}
bool cut(int l, int r) {
node *x = pool + l, *y = pool + r;
if(findroot(x) != findroot(y)) return false;
makeroot(x), access(y), splay(y);
if(y->ch[0] == x && !x->ch[1]) return y->ch[0] = x->fa = NULL, true;
return false;
}
int query(int l, int r) {
node *x = pool + l, *y = pool + r;
if(findroot(y) != findroot(x)) return -1;
makeroot(x), access(y), splay(y);
return y->tot - y->siz - 1;
}
}s;
int n, m;
int main() {
n = in(), m = in();
int p, x, y;
while(m --> 0) {
p = in(), x = in(), y = in();
if(p == 0) printf(s.link(x, y)? "OK\n" : "ILLEGAL\n");
if(p == 1) printf(s.cut(x, y)? "OK\n" : "ILLEGAL\n");
if(p == 2) {
x = s.query(x, y);
if(x == -1) printf("ILLEGAL\n");
else printf("%d.0000\n", x);
}
}
return 0;
}