T1
16248 岛屿
首先，手模发现任意操作一次即可构造出一组解。于是这题其实是构造题。
发现限制等价于每个三角形中两种颜色的边都存在。我们先考虑最外层的一个三角形，也就是一个度数为 \(2\) 的的点所在的三角形。要保证它里面两种颜色的边都存在，最简单的办法就是把它的两个度数染成两个不同的颜色。然后就等价于没有这个点，就变成了子问题，可以递归下去做了。到最后剩下一个四阶完全图直接特判掉即可。
代码
#include "island.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <array>
#include <queue>
using namespace std;
random_device rd;
mt19937 mtrand(rd());
queue<int> q;
int f[200005];
int deg[200005];
int getf(int x) { return f[x] == x ? x : (f[x] = getf(f[x])); }
int o[200005];
int cnt;
int head[200005], nxt[1000005], to[1000005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
bool vis[200005];
void construct_two_trees(int N, std::vector<int> U, std::vector<int> V){
vector<array<int, 2> > t1, t2;
for (int i = 0; i < N - 3; i++) {
deg[U[i]]++;
deg[V[i]]++;
add(U[i], V[i]);
add(V[i], U[i]);
}
cnt = N;
for (int i = 0; i < N; i++) deg[i] += 2, add(i, (i + 1) % N), add((i + 1) % N, i);
for (int i = 0; i < N; i++) {
if (deg[i] == 2)
q.push(i);
}
while (cnt > 3) {
int x = q.front();
q.pop();
--cnt;
vis[x] = 1;
int cnt = 0;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v]) {
--deg[v];
cnt ? t2.emplace_back((array<int, 2>) { x, v }) : t1.emplace_back((array<int, 2>) { x, v });
++cnt;
if (deg[v] == 2)
q.push(v);
}
}
}
int a, b, c;
a = q.front(), q.pop();
b = q.front(), q.pop();
c = q.front(), q.pop();
int x = add_vertex(a, b, c);
t1.emplace_back((array<int, 2>) { a, x });
t1.emplace_back((array<int, 2>) { x, c });
t1.emplace_back((array<int, 2>) { a, b });
t2.emplace_back((array<int, 2>) { x, b });
t2.emplace_back((array<int, 2>) { a, c });
t2.emplace_back((array<int, 2>) { b, c });
report(t1);
report(t2);
}
T2
洛谷 P11239 跳跃游戏
等价于选一堆点，使得相邻两个距离不小于 \(K\)。发现选的点要么正好和上一个相距 \(K\)，要么就是在一个同色连续段的开头。否则考虑将选的点往前移一个，发现收益不变，落点往前移了一个。而这是不劣的。
朴素 dp，然后考虑把序列每 \(K\) 个分一段，发现每个段内是不会出现互相转移的。因此依次考虑每一段，维护每个段内的 dp 值。每次往后走一段时，若这个段内没有连续段的开头，则直接做全局加。否则考虑每个连续段开头，
剩下的你先别急。
T3
洛谷 P11241 病毒
点分治优化建图板子。对每个分治中心子树内的每个深度建一个点，该深度内的每个点向它连边（或它向该深度内的每个点连边），然后每个深度的点向比它深度少 \(1\) 的点连边。然后做树上邻域连边只需要用点分树上每个父亲对应深度的点连向它即可。
代码
#include "virus.h"
#include <iostream>
#include <string.h>
#include <vector>
#include <array>
#include <queue>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
struct node {
int x, dis;
};
bool operator<(node a, node b) { return a.dis > b.dis; }
priority_queue<node> q;
int dist[5000005];
int head[5000005], nxt[10000005], to[10000005], ew[10000005], ecnt;
// void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int dep[1000005], top[1000005], son[1000005], sz[1000005], f[1000005];
void add(int u, int v, int ww = 0) {
// cout << u << " " << v << "\n";
to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, ew[ecnt] = ww;
}
int ncnt;
int c[5000005];
bool vis[5000005];
void dijkstra() {
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.x;
if (vis[x])
continue;
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (dist[v] > dist[x] + ew[i])
q.push((node) { v, dist[v] = dist[x] + ew[i] });
}
}
}
vector<int> G[2000005];
void dfs1(int x, int fa, int d) {
dep[x] = d;
f[x] = fa;
sz[x] = 1;
for (auto v : G[x]) {
if (v != fa) {
dfs1(v, x, d + 1);
sz[x] += sz[v];
sz[v] > sz[son[x]] ? (son[x] = v) : 0;
}
}
}
void dfs2(int x, int t) {
top[x] = t;
son[x] ? dfs2(son[x], t) : void();
for (auto v : G[x]) {
v != f[x] && v != son[x] ? dfs2(v, v) : void();
}
}
inline int LCA(int x, int y) {
while (top[x] ^ top[y]) (dep[top[x]] < dep[top[y]]) ? (y = f[top[y]]) : (x = f[top[x]]);
return (dep[x] < dep[y]) ? x : y;
}
inline int Dist(int x, int y) { return dep[x] + dep[y] - 2 * dep[LCA(x, y)]; }
bool mark[1000005];
int rt, all, mnv, mxdist;
vector<int> in[1000005], out[1000005];
void getroot(int x, int fa, int d = 0, int X = 0) {
mxdist = max(mxdist, d);
if (X) {
add(in[X][d], x);
add(x, out[X][d], c[x]);
}
sz[x] = 1;
int msz = 0;
for (auto v : G[x]) {
if (v != fa && !mark[v]) {
getroot(v, x, d + 1, X);
sz[x] += sz[v];
msz = max(msz, sz[v]);
}
}
msz = max(msz, all - sz[x]);
if (msz < mnv)
mnv = msz, rt = x;
}
int fa[1000005];
int mxd[1000005];
void dfs3(int x) {
mxdist = 0;
getroot(x, 0);
in[x].resize(mxdist + 1);
out[x].resize(mxdist + 1);
mxd[x] = mxdist;
for (int i = 0; i <= mxdist; i++) in[x][i] = ++ncnt;
for (int i = 0; i <= mxdist; i++) out[x][i] = ++ncnt;
for (int i = 0; i < mxdist; i++) add(in[x][i + 1], in[x][i]);
for (int i = 0; i < mxdist; i++) add(out[x][i], out[x][i + 1]);
add(in[x][0], x);
add(x, out[x][0], c[x]);
mark[x] = 1;
for (auto v : G[x]) {
if (!mark[v]) {
all = sz[v], rt = 0, mnv = inf, mxdist = 0;
getroot(v, x, 1, x);
fa[rt] = x;
dfs3(rt);
}
}
}
void Add(int x, int lim, int X) {
int u = x;
while (u) {
int d = Dist(u, x);
if (lim >= d) {
add(X, in[u][min(mxd[u], lim - d)]);
add(out[u][min(mxd[u], lim - d)], X);
}
u = fa[u];
}
}
#undef int
vector<long long> find_spread(int N, int M, vector<int> A, vector<int> B, vector<int> P, vector<int> D, vector<int> C) {
#define int long long
memset(dist, 63, sizeof dist);
ncnt = N + M;
for (int i = 0; i < N - 1; i++) G[A[i] + 1].emplace_back(B[i] + 1), G[B[i] + 1].emplace_back(A[i] + 1);
for (int i = 0; i < N; i++) c[i + 1] = C[i];
vector<int> ret;
dfs1(1, 0, 1);
dfs2(1, 1);
all = N, mnv = N + 1;
getroot(1, 0);
dfs3(rt);
// for (int i = 1; i <= N; i++) cerr << fa[i] << " ";
// cerr << "\n";
for (int i = 1; i <= M; i++) Add(P[i - 1] + 1, D[i - 1], i + N);
q.push((node) { N + 1, dist[N + 1] = 0 });
dijkstra();
for (int i = 1; i <= M; i++) {
if (dist[N + i] >= inf)
ret.emplace_back(-1);
else
ret.emplace_back(dist[N + i]);
}
return ret;
}
T4
2552 树
首先不难想到任意定根将树分层，然后只需要确定相邻两层间的祖先关系。假设当前父亲层点集为 \(A\)，儿子层点集为 \(B\)，我们随机将 \(A\) 平均分成两半，设其中一半为 \(A_r\)。则 \(A\) 中一个点 \(i\) 是 \(B\) 中点 \(j\) 的父亲当且仅当 \(ask(i, A_r) + |A_r| = ask(j, A_r)\)。这样就可以将 \(A\) 中点按 \(ask(i, A_r)\) 分组，将 \(B\) 中点按 \(ask(j, A_r)\) 分组，则所有祖先关系进一步被确定在两层的对应组之间。因此再对于每一组递归求解即可。询问次数 \(\mathcal{O}(n \log n)\)，最坏情况不超过九千多。
代码
#include "tree.h"
#include <iostream>
#include <random>
#include <vector>
using namespace std;
random_device rd;
mt19937 mtrand(rd());
int fa[1005], dep[1005];
vector<int> vec[1005];
inline int dist(int x, int y) {
int ret = 0;
while (x ^ y) (dep[x] < dep[y]) ? (y = fa[y]) : (x = fa[x]), ++ret;
return ret;
}
void Solve(vector<int> A, vector<int> B) {
if (!A.size())
return;
if ((int)A.size() == 1) {
for (auto v : B) answer(v, fa[v] = A[0]);
return;
}
vector<int> Ar;
shuffle(A.begin(), A.end(), mtrand);
for (int i = 0; i * 2 < (int)A.size(); i++) Ar.emplace_back(A[i]);
map<int, vector<int> > mp1, mp2;
for (auto v : A) {
int tmp = 0;
for (auto w : Ar) tmp += dist(v, w) + 1;
mp1[tmp].emplace_back(v);
}
for (auto v : B) mp2[ask(v, Ar)].emplace_back(v);
for (auto v : mp2) Solve(mp1[v.first], v.second);
}
void solver(int n, int A, int B) {
int rt = mtrand() % n + 1;
for (int i = 1; i <= n; i++) vec[dep[i] = ask(rt, (vector<int>) { i })].emplace_back(i);
for (int i = 0; i <= n; i++) Solve(vec[i], vec[i + 1]);
}