如题

#include <bits/stdc++.h>
#include "rts.h"
#define il inline
const int N = 3e5;
using namespace std;
// int explore(int,int);

namespace chain {
	bool used[N + 10];
	int n, T;
	vector <int> ord;
	void init(int nn, int tt) {
		n = nn, T = tt;
		for(int i = 2; i <= n; i++)
			ord.push_back(i);
		for(int t = 1; t <= 10; t++)
			random_shuffle(ord.begin(), ord.end());
		used[1] = 1;
		int L = 1, R = 1;
		for(int i = 0; i < ord.size(); i++) {
			if(used[ord[i]]) continue;
			int o = rand() % 2;
			int w = explore(((o == 0) ? R : L), ord[i]);
			if(!used[w]) {
				used[w] = 1;
				int x = w;
				while(x != ord[i])
					x = explore(x, ord[i]), 
					used[x] = 1;
				if(o == 0) R = ord[i];
				else L = ord[i];
			}
			else {
				w = explore(((o == 0) ? L : R), ord[i]);
				used[w] = 1;
				int x = w;
				while(x != ord[i])
					x = explore(x, ord[i]), 
					used[x] = 1;

				if(o == 1) R = ord[i];
				else L = ord[i];
			}
		}
	}
}
namespace tree {
	unordered_map <int, unordered_map <int, int> > M;
	vector <int> gra[N + 10];
	int fat[N + 10];
	vector <int> T[N + 10];
	int root = 0;
	int sz[N + 10];

	bool used[N + 10];
	int pot = 0;

	int n;
	il int getson(int u, int aim) {
		while(fat[u] != aim)
			u = fat[u];
		return u;
	}
	vector <int> dot;
	bool isin[N + 10], vis[N + 10];
	int cur[N + 10], tc = 0;
	il void getdot(int u) {
		cur[++tc] = u;
		isin[u] = 1;
		vis[u] = 0;
		for(int i = 0; i < T[u].size(); i++) {
			int v = T[u][i];
			getdot(v);
		}
		T[u].clear();
	}
	int siz[N + 10], mxz[N + 10];//in gra[] the siz
	int rem = 0, maxpart = N, nowroot = 0;
	il void getsiz(int u, int fa) {
		siz[u] = 1;
		mxz[u] = 0;
		for(int i = 0; i < gra[u].size(); i++) {
			int v = gra[u][i];
			if(vis[v] || !isin[v] || v == fa) continue;
			getsiz(v, u);
			siz[u] += siz[v];
			mxz[u] = max(mxz[u], siz[v]);
		}
	} 
	il int getroot(int u, int fa) {
		if(max(mxz[u], rem - siz[u]) <= rem / 2) return u;
		for(int i = 0; i < gra[u].size(); i++) {
			int v = gra[u][i];
			if(vis[v] || !isin[v] || v == fa) continue;
			int t = getroot(v, u);
			if(t != -1) return t;
		}
		return -1;
	}
	il void rb(int u) {
		vis[u] = 1;
		sz[u] = 1;
		for(int i = 0; i < gra[u].size(); i++) {
			int v = gra[u][i];
			if(vis[v] || !isin[v]) continue;
			getsiz(v, 0);
			rem = siz[v], maxpart = N, nowroot = getroot(v, 0);
			int ww = nowroot;
			T[u].push_back(ww);
			fat[ww] = u;
			rb(ww);
			sz[u] += sz[ww];
		}
	}
	il void rebuild(int u) {
		getdot(u);
		getsiz(u, 0);
		rem = siz[u], maxpart = N, nowroot = getroot(u, 0);
		if(nowroot != u && fat[u]) {
			vector <int> tmp = T[fat[u]];
			T[fat[u]].clear();
			for(int i = 0; i < tmp.size(); i++)
				if(tmp[i] != u) T[fat[u]].push_back(tmp[i]);
			T[fat[u]].push_back(nowroot);
			fat[nowroot] = fat[u];
		}
		if(!fat[u]) {
			sz[nowroot] = sz[root];
			root = nowroot;
			fat[nowroot] = 0;
		}
		rb(nowroot);
		for(int i = 1; i <= tc; i++) 
			isin[cur[i]] = vis[cur[i]] = 0;
		tc = 0;
	}
	int path[N + 10], tt = 0;
	il void find(int aim) {
		int x = root, bl = 0;
		while(1) {
			int z;
			if(M[x][aim]) z = M[x][aim];
			else z = M[x][aim] = explore(x, aim);
			bl = z;
			if(!used[z]) {
				gra[x].push_back(z);
				gra[z].push_back(x);
				T[x].push_back(z);
				fat[z] = x;
				used[z] = 1;
				break;
			}
			else
				x = getson(z, x);
		}
		tt = 0;
		x = bl;
		while(x) {
			path[++tt] = x;
			sz[x]++;
			x = fat[x];
		}
		for(int i = tt; i >= 2; i--) {
			int a = path[i], b = path[i - 1];
			if((double)(0.75 * sz[a]) < (double)(1.0 * sz[b])) {
				rebuild(a);
				return ;
			}
		}
	}
	void init(int nn) {
		n = nn;
		used[1] = 1;
		root = 1;
		sz[1] = 1;
		
		vector <int> ord;
		for(int i = 2; i <= n; i++)
			ord.push_back(i);
		random_shuffle(ord.begin(), ord.end());
		random_shuffle(ord.begin(), ord.end());

		for(int i = 0; i < ord.size(); i++) {
			int v = ord[i];
			while(!used[v]) 
				find(v);
		}
	}
}
void play(int n, int T, int dataType) {
	srand(20090725);
	if(dataType == 3) chain::init(n, T);
	else tree::init(n);
}

这个代码 95pts，loj 可以勉强卡过去，uoj 和 洛谷 都过不去，求助卡常 QAQ