一身素青纱 ⚡ 草柄当头花 ⚡
A - Maximum Diameter
https://www.luogu.com.cn/problem/AT_abc290_f
考虑一个固定的序列，很容易发现可以用叶子来调整，使得树成为毛毛虫。
故最长直径为 \(n-cnt_1+2\)，其中 \(cnt_1\) 为叶子个数。
发现只需要 \(\forall\,i,a_i>0\) 且 \(\sum a_i=2n-2\)，那么就有解。枚举叶子个数 \(k\) 再插板法算方案，得到答案为：
\[ \sum_{k=2}^{n-1} \binom{2n-2-k-(n-k)-1}{n-k-1}\times \binom nk\times (n-k+1) \]
BB：注意边数比点数少 1。
题目没保证 \(\sum n\) 的范围，系数会变也不太方便预处理，考虑变形：
\[ \begin{aligned} &\sum_{k=2}^{n-1} \binom{n-3}{k-2}\times \binom n{k}\times (n-k+1)\\ =&(n+1)\sum_{k=2}^{n-1} \binom{n-3}{k-2}\times \binom n{k}-\sum_{k=2}^{n-1} k\times \binom n{k}\times \binom{n-3}{k-2}\\ =&(n+1)\binom{2n-3}{n-2}-n\times \sum_{k=2}^{n-1} \binom {n-1}{k-1}\times \binom{n-3}{k-2}\\ =&(n+1)\times\binom{2n-3}{n-2}-n\times\binom{2n-4}{n-2}\\ \end{aligned} \]
用到了：\(k\cdot C_n^k=n\cdot C_{n-1}^{k-1}\)、范德蒙德卷积 \(\sum_{i=0}^k C_n^i\cdot C_m^{k-i}=C_{n+m}^k\)。
只想说这种只涉及到高中组合知识，且放到高考数学卷子里我都拿不到分的式子就不要拿来考我了 :-)
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
const int N = 2e6;
std::vector<long long> fac(N + 1), inv(N + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= N; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[N] = qkp(fac[N], mod - 2);
for (int i = N - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[m] % mod * inv[n - m] % mod;
};
int T;
for (std::cin >> T; T--; ) {
int n;
std::cin >> n;
std::cout << ((n + 1) * C(2 * n - 3, n - 2) + mod - n * C(2 * n - 4, n - 2) % mod) % mod << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B - Game on Graph
https://www.luogu.com.cn/problem/AT_abc261_h
merchant 统治全世界……
令 \(f_{u,0/1}\) 表示在 \(x\) 点且 A / B 执棋时的代价。则：
\[ f_{u,0}\gets \min\{f_{v,1}+w\}\\ f_{u,1}\gets \max\{f_{v,0}+w\} \]
容易发现这大概是一个 Dij 的结构，对于出度为 \(0\) 的点 \(u\) 有 \(f_{u,0}=f_{u,1}=0\)，且出度为 \(0\) 恰好符合拓扑序，可以参照 merchant 中的处理方式，以 \(f_{*,0}\) 为主体做最短路 Dij，待 \(f_{*,1}\) 的出边将其更新完后加入优先队列（容易发现这个拓扑结构让它只会入队一次）。
虽然过程很简单，但是思想很巧妙。总之可以看一看，结合 merchant 思考一下。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
const long long inf = 1e18;
int n, m, s;
std::cin >> n >> m >> s;
std::vector<int> deg(n + 1);
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
for (int x, y, w; m--; ) {
std::cin >> x >> y >> w;
g[y].emplace_back(x, w);
++deg[x];
}
std::vector<int> vis(n + 1);
std::vector<std::vector<long long> > dis(n + 1, std::vector<long long> (2));
struct node {
long long w;
int k, x;
bool operator< (const node &q) const {
return w > q.w;
}
};
std::priority_queue<node> q;
for (int i = 1; i <= n; ++i)
if (!deg[i]) {
dis[i][0] = dis[i][1] = 0ll;
q.push({ 0ll, 0, i });
q.push({ 0ll, 1, i });
}
else
dis[i][0] = inf;
for (; !q.empty(); ) {
auto [d, k, x] = q.top();
q.pop();
if (k == 0) {
if (vis[x])
continue;
vis[x] = 1;
for (auto [i, w] : g[x]) {
dis[i][1] = std::max(dis[i][1], std::min(d + w, inf));
if (!--deg[i])
q.push({ dis[i][1], 1, i });
}
}
else
for (auto [i, w] : g[x])
if (dis[i][0] > d + w) {
dis[i][0] = d + w;
q.push({ dis[i][0], 0, i });
}
}
if (dis[s][0] == inf)
std::cout << "INFINITY\n";
else
std::cout << dis[s][0] << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C - Vertex Pairs
https://www.luogu.com.cn/problem/CF2042E
全新做法
有一个 naive 的想法：check 删去 \(n\) 后是否存在合法连通块。
如果存在，则至少有一个元素（\(a_n\)）只被一个连通块包含，那么答案连通块一定是这一个。
否则，说明 \(n\) 必选——这种情况当且仅当 \(n\) 的每一个子树（父亲）都不包含所有值时出现。
扩展一下，DFS 序 + 线段树统计信息（DS 大师自有办法），找到最后一个不必选的点，然后把它裂开，找到唯一合法连通块，抹掉被删掉的所有点的信息，重复这个过程即可，复杂度很对。
至于怎么统计这样的信息，点是两两配对的，以 DFS 序记录每一对 \((l, r)\)，对于 \(x\) 的子树，其存在不包含的值当且仅当，DFS 序区间落在 \([1,l)\)，或 \((l, r)\)，或 \((r+1,n)\)。维护每个 \(i\) 作为左端点，需求的最小右端点即可。
对于父亲方向的连通块，其存在不包含的值当且仅当，有某个 \([l,r]\) 完全落在 \(x\) 内。同样是好维护的。
这样就获得了 \(O(n\log n)\) 的暴力 DS 做法。没有任何思维点！
#include <bits/stdc++.h>
const int maxn = 4e5 + 5;
struct {
int l, r, u, mn, d;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void bld(int p, int l, int r) {
t[p].mn = 0x3f3f3f3f;
t[p].l = l, t[p].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void pushdown(int p) {
if (t[p].d) {
t[lt].u = std::max(t[lt].u, t[p].d);
t[lt].d = std::max(t[lt].d, t[p].d);
t[rt].u = std::max(t[rt].u, t[p].d);
t[rt].d = std::max(t[rt].d, t[p].d);
t[p].d = 0;
}
return;
}
void add(int p, int x, int v) {
t[p].mn = std::min(t[p].mn, v);
if (t[p].l == t[p].r)
return;
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
add(lt, x, v);
else
add(rt, x, v);
return;
}
void add(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].u = std::max(t[p].u, v);
t[p].d = std::max(t[p].d, v);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
t[p].u = std::max(t[lt].u, t[rt].u);
return;
}
int asku(int p, int x) {
if (t[p].l == t[p].r)
return t[p].u;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
return asku(lt, x);
return asku(rt, x);
}
int askmn(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].mn;
int mid = (t[p].l + t[p].r) >> 1, res = 0x3f3f3f3f;
if (l <= mid)
res = askmn(lt, l, r);
if (r > mid)
res = std::min(res, askmn(rt, l, r));
return res;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<int> a(2 * n + 1);
for (int i = 1; i <= 2 * n; ++i)
std::cin >> a[i];
std::vector<std::vector<int> > g(2 * n + 1);
for (int i = 1, x, y; i < 2 * n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> dfn(2 * n + 1), rfn(2 * n + 1), fa(2 * n + 1), s(n + 1);
std::function<void(int)> DFS = [&](int x) {
static int now = 0;
dfn[x] = ++now, s[a[x]] += now;
for (auto i : g[x])
if (i != fa[x])
fa[i] = x, DFS(i);
rfn[x] = now;
return;
};
DFS(1);
std::vector<int> la(n + 1);
bld(1, 1, 2 * n);
for (int i = 1; i <= 2 * n; ++i)
if (la[a[i]]) {
int l = dfn[la[a[i]]], r = dfn[i];
if (l > r)
std::swap(l, r);
add(1, l, r);
if (l != 1)
add(1, 1, l - 1, l);
if (l + 1 <= r - 1)
add(1, l + 1, r - 1, r);
if (r != 2 * n)
add(1, r + 1, 2 * n, 0x3f3f3f3f);
}
else
la[a[i]] = i;
std::vector<int> del(2 * n + 1), res;
for (int i = 2 * n; i; --i)
if (!del[i]) {
int to = 0;
for (auto j : g[i])
if (!del[j] && j != fa[i] && asku(1, dfn[j]) <= rfn[j]) {
to = j;
break;
}
if (!to && (!fa[i] || del[fa[i]] || askmn(1, dfn[i], rfn[i]) <= rfn[i]))
res.push_back(i);
else {
std::function<void(int, int)> DFS = [&](int x, int fa) {
assert(s[a[x]] > dfn[x]);
s[a[x]] -= dfn[x];
add(1, s[a[x]], s[a[x]]);
if (s[a[x]] < dfn[x]) {
if (s[a[x]] != 2 * n)
add(1, s[a[x]] + 1, 2 * n, 0x3f3f3f3f);
}
else
add(1, 1, s[a[x]], s[a[x]]);
del[x] = 1;
for (auto i : g[x])
if (!del[i] && i != fa)
DFS(i, x);
return;
};
DFS(i, to ? to : fa[i]);
}
}
std::cout << (int)res.size() << '\n';
std::reverse(res.begin(), res.end());
for (auto i : res)
std::cout << i << ' ';
std::cout << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}D - Tree and Hamilton Path
https://www.luogu.com.cn/problem/AT_agc018_d
很难
如果问的是哈密顿回路，做法：
枚举每条边 \((u, v)\)
