[JOISC 2019 Day1]聚会

总有一些人认为做智商题就能提高智商，这种想法就像吃被门挤了的核桃不能补脑一样愚蠢。

今天我Taduro就要像他们证明：做再多神仙题我仍然是个傻子！

这不是我开始做JOI的理由

传送门

JOI真是毒瘤，我永远不能去做JOI。——潮

反正就是非常神仙的一道题就是了，据说正解是虚树+二分，太神仙了根本看不懂。

于是从奇怪的地方找到了乱搞做法。

钦定x点为根，然后随便随机一个点y，枚举当前在x的子树中的点z，如果$Query(x,y,z)$的答案是z的话，那么z在$x->y$的链上，否则，这个查出来的点在z的子树里。

这么一遍下来就得到了$x->y$这条链上的所有点和它们的子树里所有的点，但这时这条链上的点是无序的，要对其进行排序。

对于链上的点i和j，如果i比j靠近x，那么$Query(x,i,j)$应该是i，这样就排好了。

对于每个点的子树递归处理即可。存储子树和链开一个vector就好了。

#include"meetings.h"
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int k,n;
inline void bridge(int x,int y){
    if (x>y) swap(x,y);
//	printf("%d %d\n",x,y);
    Bridge(x,y);
}
inline bool cmp(int x,int y){
    return Query(k,x,y)==x;
}
void solve(vector<int> v,int rt){
    int sz=v.size(); k=rt;
    if (sz==1){
        bridge(rt,v[0]);
        return;
    }
    vector<int> q;
    vector<vector<int> > g(n);
    int y=v[rand()%sz];
    for (int i=0; i<sz; i++){
        if (v[i]==y) continue;
        int z=Query(rt,v[i],y);
        if (z==v[i]) q.push_back(v[i]);
        else
            g[z].push_back(v[i]);
    }
    sort(q.begin(),q.end(),cmp); q.push_back(y);
    bridge(rt,q[0]);
    for (int i=0; i<q.size()-1; i++) bridge(q[i],q[i+1]);
    if (g[rt].size()) solve(g[rt],rt);
    for (int i=0; i<q.size(); i++)
        if (g[q[i]].size()) solve(g[q[i]],q[i]);
}
void Solve(int N){
    n=N;
    srand(20190921);
    vector<int> v;
    for (int i=1; i<n; i++) v.push_back(i);
    solve(v,0);
}