[JOISC2019] 聚会 题解

随机化好题，但是不会证。

考虑把树看成一条链，链的每个点上缀了一棵树。

那么先随机出两个点 \(x,y\)（实际上随机一个点，另一个点固定似乎更好？），然后对于当前这棵树上的任意点 \(z\)，都让他进行一次询问，答案为 \(o=Q(x,y,z)\)。

那么当 \(o=z\) 时，显然 \(z\) 在链上，否则 \(z\) 在 \(o\) 的子树中。

对于每个链上的点的子树，递归处理就可以；而链的形态，直接对链进行排序即可，\(cmp\) 函数容易想到，就是 \([Q(x,a,b)=a]\)。

排序询问次数为 \(O(l\log l)\)，确定子树询问次数为 \(O(m)\)，其中 \(l\) 为链长，\(m\) 为当前子树大小。由于度数很小，可以通过，而且非常优秀。

#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
int Query(int u,int v,int w);
void Bridge(int u,int v);
const int N=2005;int rt;
mt19937 rnd(20100226);
void bridge(int u,int v){
	if(u>v) swap(u,v);
	Bridge(u,v);
}int cmp(int x,int y){
	return Query(rt,x,y)==x;
}void build(vector<int>g,int x){
	int n=g.size();if(n==1) return;
	if(n==2) return bridge(g[0],g[1]);
	int y=g[rnd()%n];vector<int>ve,v[N];
	while(y==x) y=g[rnd()%n];
	ve.push_back(x),ve.push_back(y);
	v[x].push_back(x),v[y].push_back(y);
	for(auto nw:g){
		if(nw==x||nw==y) continue;
		int fa=Query(x,y,nw);
		if(fa==nw) ve.push_back(nw);
		v[fa].push_back(nw);
	}rt=x,sort(ve.begin()+1,ve.end(),cmp);
	for(int i=0;i<ve.size();i++){
		if(i) bridge(ve[i-1],ve[i]);
		build(v[ve[i]],ve[i]);
	}
}void Solve(int n){
	vector<int>g;
	for(int i=0;i<n;i++)
		g.push_back(i);
	build(g,0);
}