2023冲刺国赛模拟 2.1
T1 树
首先考虑初始节点只有 \(1\) 个的情况，很容易使用 dp 解决，设 \(f_i\) 表示初始节点为 \(i\) ，占领以 \(i\) 为根的子树所需要的最小回合数量，只需要优先占领回合多的子树即可。
当初始节点为 \(2\) 个时，容易发现 \(u,v\) 路径上存在一条边，满足最优方案下 \(u,v\) 的士兵均不会跨过这条边，因此可以枚举这条边并对边两侧的子树分别 dp ，容易发现 \(u,v\) 两侧的 dp 值随着边位置的单调移动具有单调性，因此可以二分两侧 dp 值最接近的位置，这个位置取到最优方案。
直接做复杂度为 \(O(n\log^2 n)\) ，考虑进行优化，容易发现每次进行 dp 进行了许多重复的计算，因此考虑断掉链上所有边预处理每个地方的 dp 值，二分 check 时只需要连接链即可，此时我们相当于在原先节点下连接一棵子树，设当前连接的子树的贡献为 \(res\) ，此时我们需要将 \(res\) 插入到对应节点的子树序列中，我们设原先这个节点 \(i\) 取到最大 dp 值的位置为 \(pos\) ，如果 \(res\) 可以插入到 \(pos\) 之前，显然会产生 \(f_i+1\) 的贡献，否则产生 \(f_i\) 的贡献，同时考虑到 \(res\) 插入到序列开头贡献为 \(res+1\) ，对这几种贡献取 \(\max\) 即可，复杂度为 \(O(n\log n)\) 。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
const int max1 = 5e5, B = 30;
const int inf = 0x3f3f3f3f;
int n, a, b;
struct Node
{ int next, v; } edge[max1 * 2 + 5];
int head[max1 + 5], total;
int father[max1 + 5], seq[max1 + 5], len;
bool vis[max1 + 5];
int f[max1 + 5], maxpos[max1 + 5], ans;
vector <int> tmp;
void Add ( int u, int v )
{
edge[++total].v = v;
edge[total].next = head[u];
head[u] = total;
return;
}
void Dfs ( int now, int fa, int pre_edge )
{
father[now] = fa;
for ( int i = head[now]; i; i = edge[i].next )
{
int v = edge[i].v;
if ( v == fa )
continue;
Dfs(v, now, i);
}
return;
}
void Redfs ( int now, int fa )
{
for ( int i = head[now]; i; i = edge[i].next )
{
int v = edge[i].v;
if ( v == fa || vis[v] )
continue;
Redfs(v, now);
}
tmp.clear();
for ( int i = head[now]; i; i = edge[i].next )
{
int v = edge[i].v;
if ( v == fa || vis[v] )
continue;
tmp.push_back(f[v]);
}
sort(tmp.begin(), tmp.end());
reverse(tmp.begin(), tmp.end());
f[now] = 0; maxpos[now] = -1;
int siz = tmp.size();
for ( int i = 0; i < siz; i ++ )
{
if ( f[now] <= i + 1 + tmp[i] )
{
f[now] = i + 1 + tmp[i];
maxpos[now] = tmp[i];
}
}
return;
}
bool Check ( int mid )
{
int A = f[seq[mid + 1]], B = f[seq[mid]];
for ( int i = mid + 2; i <= len; i ++ )
A = max(f[seq[i]] + ( A >= maxpos[seq[i]] ), A + 1);
for ( int i = mid - 1; i >= 1; i -- )
B = max(f[seq[i]] + ( B >= maxpos[seq[i]] ), B + 1);
return A < B;
}
int Query ( int mid )
{
int A = f[seq[mid + 1]], B = f[seq[mid]];
for ( int i = mid + 2; i <= len; i ++ )
A = max(f[seq[i]] + ( A >= maxpos[seq[i]] ), A + 1);
for ( int i = mid - 1; i >= 1; i -- )
B = max(f[seq[i]] + ( B >= maxpos[seq[i]] ), B + 1);
return max(A, B);
}
int main ()
{
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d%d%d", &n, &a, &b); total = 1;
for ( int i = 2, u, v; i <= n; i ++ )
{
scanf("%d%d", &u, &v);
Add(u, v), Add(v, u);
}
Dfs(a, 0, 0);
int now = b;
while ( now )
{
seq[++len] = now;
vis[now] = true;
now = father[now];
}
for ( int i = 1; i <= len; i ++ )
Redfs(seq[i], 0);
int L = 1, R = len - 1, pos = len - 1;
while ( L <= R )
{
int mid = L + R >> 1;
if ( Check(mid) )
pos = mid, R = mid - 1;
else
L = mid + 1;
}
ans = Query(pos);
if ( pos > 1 )
ans = min(ans, Query(pos - 1));
printf("%d\n", ans);
return 0;
}
T2 最小生成树
假设当前我们已经知道所有树边权值的相对大小关系，考虑统计非树边产生的贡献。
有一个经典结论：非树边连接端点 \(u,v\) 满足非树边权值大于 \(u,v\) 对应最小生成树的路径上边权最大值。
从边权较小的边向较大的边连边，可以得到拓扑关系图，去掉不必要的边后发现树边构成一条链，链上每个节点连接一些非树边，此时我们的目的是统计拓扑序的方案数，设每个节点下连接的非树边个数为 \(w_i\) ，考虑按照 \(w_i\) 个非树边， \(1\) 个树边的顺序依次插入到拓扑序中。
设当前加入的边的总数为 \(n\) ，树边有 \(b\) 个，方案数为 \(c\) 个，所有方案的树边位置和为 \(s\) 。
考虑加入一条树边，由于只能插入到序列开头，因此变化为：
考虑加入一条非树边，变化为：
简单解释一下 \(s\to s(n+2)\) ，首先一个基础的方案数的贡献为 \(s(n+1)\) ，之后树边所在的位置 \(A\) ，容易发现存在 \(A\) 种方案满足这个树边的位置 \(+1\) ，不难发现这部分的贡献和为 \(s\) 。
考虑加入 \(w_i\) 条非树边，变化为：