XJOI的模拟赛，（一个账号提前交卷了出了一些锅），不过还是顺利AK。

【A 吉利挖矿】

【题解】这种题啊一看就是二分答案然后乱搞啦！

非常兹磁！$O(nhlog~a_{i,j})$

# include <stdio.h>
# include <vector>
// # include <bits/stdc++.h>

using namespace std;

int n, h;

const double eps = 1e-5, fineps = 1e-8;
vector<int> a[100010];
vector<double> b[100010];

inline bool check(double x) {
	
	for (int i=1; i<=n; ++i) b[i].clear();
	
	for (int i=1; i<=n; ++i)
		for (int j=0; j<h; ++j)
			b[i].push_back((double)a[i][j]-x);
	
	/*
	for (int i=1; i<=n; ++i, printf("\n"))
		for (int j=0; j<h; ++j)
			printf("%.4lf ", b[i][j]);
	puts("==================");	
	*/
	
	double maxx = 0;
	
	for (int i=1; i<=n; ++i) {
		double s=0, cur=-1e9-1;
		for (int j=0; j<h; ++j) {
			s=s+b[i][j];
			if(s>cur) cur=s;
		}
		maxx=maxx+cur;
	}
	
	return maxx>=-fineps;
}

int main() {
	scanf("%d%d", &n, &h);
	for (int i=1, x; i<=n; ++i) {
		for (int j=1; j<=h; ++j) {
			scanf("%d", &x);
			a[i].push_back(x);
		}
	}
	
	double l, r, mid;
	l = -1e9-1, r = 1e9+1;
	while(1) {
		if(r-l<=eps) break;
		mid = (l+r) / 2.0;
		if(check(mid)) l = mid;
		else r = mid;
	}
	
	printf("%.4lf\n", l);

	return 0;
}

【B 吉利的道路】

见xiaone校内训练Round1 T1：这里。

【C 膜拜吉利】

【题解】对于操作1，我们可以暴力维护，操作2我们用类似于LCA的往上跳即可，因为膜拜吉利的人一定从下到上集中在几层里，所以就能维护啦，至于怎么维护从小到大？搞LCA的时候排排序啊，DFS序搞搞就行了。

因为会随时push，所以用priority_queue。

Tips： priority_queue<int, vector<int>, greater<int>>是小根堆。

# include <stdio.h>
# include <algorithm>
# include <queue>
# include <vector>
// # include <bits/stdc++.h>

using namespace std;

const int M = 400010, N = 200010, logN = 19;
# define next nxt 
int tot=0, next[M], head[N], to[M];
int n, Q;
int fa[N][logN], dep[N]; 
priority_queue< int, vector<int>, greater<int> > q;
bool ok[N]; 
int dfn[N], ndfn[N], DFN=0; 


inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int fat, int depth) {
	vector<int> v;
	dep[x]=depth; fa[x][0]=fat;
	for (int i=1; i<logN; ++i)
		fa[x][i] = fa[fa[x][i-1]][i-1];
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fat) continue;
		v.push_back(to[i]); 
	}
	sort(v.begin(), v.end());
	int ttx = v.size(); 
	for (int i=0; i<ttx; ++i)
		dfs(v[i], x, depth+1);
	dfn[x]=++DFN;
	ndfn[DFN]=x;
}

int main() {
	scanf("%d%d", &n, &Q); 
	for (int i=1, u, v; i<n; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 0, 1);
	for (int i=1; i<=n; ++i) q.push(i);
	while(Q--) {
		int opt, x;
		scanf("%d%d", &opt, &x);
		if(opt == 1) {
			int t = 0;
			while(x--) {
				t = q.top(); 
				ok[t]=1;
				q.pop();
			}
			printf("%d\n", ndfn[t]); 
		} else if (opt == 2) {
			int tx = x;
			for (int i=logN-1; i>=0; --i) 
				if(fa[tx][i] != 0 && ok[dfn[fa[tx][i]]]) tx = fa[tx][i];
			ok[dfn[tx]]=0;
			q.push(dfn[tx]); 
			printf("%d\n", abs(dep[x] - dep[tx])); 
		}
	}

	return 0;
}