「WC2018即时战略」
题目描述
小 M 在玩一个即时战略 (Real Time Strategy) 游戏。不同于大多数同类游戏，这个游戏的地图是树形的。也就是说，地图可以用一个由 \(n\) 个结点，\(n - 1\) 条边构成的连通图来表示。这些结点被编号为 \(1 \sim n\)。
每个结点有两种可能的状态：“已知的”或“未知的”。游戏开始时，只有 \(1\) 号结点是已知的。
在游戏的过程中，小 M 可以尝试探索更多的结点。具体来说，小 M 每次操作时需要选择一个已知的结点 \(x\)，和一个不同于 \(x\) 的任意结点 \(y\)（结点 \(y\) 可以是未知的）。然后游戏的自动寻路系统会给出 \(x\) 到 \(y\) 的最短路径上的第二个结点 \(z\)，也就是从 \(x\) 走到 \(y\) 的最短路径上与 \(x\) 相邻的结点。此时，如果结点 \(z\) 是未知的，小 M 会将它标记为已知的。这个游戏的目标是：利用至多 \(T\) 次探索操作，让所有结点的状态都成为已知的。然而小 M 还是这个游戏的新手，她希望得到你的帮助。
解题思路 :
首先有一个比较直观的暴力，random_shuffle一个询问顺序，同时维护一棵“已知树”。
每次从根节点开始询问，回答要么是当前点的儿子，要么是一个未知节点，如果是当前点的儿子就进入儿子节点，否则就把未知节点添加进树。
这样子做复杂度和询问次数都是 \(O(n^2)\)，加上一条链的暴力可以得到 \(65\) 分。
实际上每次如果是已知节点的话，只需要进入儿子对应的子树询问即可，所以很容易想到用点分树维护这个“已知树”，每次直接找到这个儿子对应的点分中心进行询问，树高变成 \(logn\) 。
但是加点操作会破坏点分树的性质，使得树高会大于 \(logn\) 以至于退化到平方级别的复杂度，在这里可以用替罪羊树的思想，每次加完点后暴力向上检查子树的平衡性暴力重构，\(\alpha\) 这里一般设 \(0.7\) 。
不过由于我维护点分树信息的时候用 \(map\) 存了每个儿子对应的点分中心是什么，所以我的复杂度是 $O(nlog^2n) $ ，有点卡常数，不保证所有地方都能过。
#include "rts.h"
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
const int N = 1000005;
map<int, int> mp[N], ss[N];
int vis[N], vi[N], sz[N], in[N], cc[N], mx[N], fa[N];
int size[N], id[N], ps[N], all, mn, rt, Root = 1;
map<int, int>::iterator it;
namespace Line{
int s[2] = {1, 1};
inline void solve(int n){
for(int i = 1, x; i < n; i++){
int now = id[i], tw = 1;
while(!vis[now]){
x = explore(s[tw], now);
if(vis[x]) x = explore(s[tw^=1], now);
vis[x] = 1, s[tw] = x;
}
}
}
}
inline void cleartag(int u){
in[u] = 1;
for(map<int,int>::iterator it = mp[u].begin(); it != mp[u].end(); it++)
if(it->second) cleartag(it->second);
}
inline void getsize(int u, int ff){
int now = 0; sz[u] = 1;
for(map<int, int>::iterator it = mp[u].begin(); it != mp[u].end(); it++){
int v = it->first;
if(v == ff || !in[v]) continue;
getsize(v, u), sz[u] += sz[v];
if(sz[v] >= now) now = sz[v];
}
now = max(now, all - sz[u]);
if(now <= mn) mn = now, rt = u;
}
inline void rebuild(int u){
int last = all; in[u] = 0;
for(map<int, int>::iterator it = mp[u].begin(); it != mp[u].end(); it++){
int v = it->first;
if(!in[v]) continue;
mn = all = sz[v] >= sz[u] ? last - sz[u] : sz[v];
getsize(v, u);
size[rt] = all, fa[rt] = u, mx[u] = Max(mx[u], all);
mp[u][v] = rt, ss[u][rt] = v, mp[v][u] = 0, rebuild(rt);
}
}
inline void update(int u){
int ned = 0;
for(int x = u; x != Root; x = fa[x]){
size[fa[x]]++;
if(size[x] > mx[fa[x]]) mx[fa[x]] = size[x];
if(mx[fa[x]] >= size[fa[x]] * 0.735) ned = fa[x];
}
if(!ned) return;
if(ned){
cleartag(ned);
all = mn = size[ned], getsize(ned, fa[ned]);
if(ned == Root) Root = rt;
size[rt] = all, fa[rt] = fa[ned];
int k = ss[fa[rt]][ned];
ss[fa[rt]][rt] = k, mp[fa[rt]][k] = rt, rebuild(rt);
}
}
inline void addnode(int pos){
for(register int u = Root; ; ){
int x = explore(u, pos);
if(!vis[x]){
fa[x] = u, size[x] = vis[x] = 1;
mp[u][x] = ss[u][x] = x, mp[x][u] = 0, update(x);
break;
} u = mp[u][x];
}
}
void play(int n, int T, int datatype){
srand(19262333);
for(int i = 1; i < n; i++) id[i] = i + 1;
random_shuffle(id + 1, id + n), vis[1] = 1;
if(datatype == 3) return (void) (Line::solve(n));
for(int i = 1; i < n; i++) while(!vis[id[i]]) addnode(id[i]);
}