Description
对于一个 $n$ 个结点的带边权的树 $T$，定义 $dis(x,y)$ 为 $T$ 中 $x\to y$ 路径上的边权和。再定义一个 $n$ 个结点的无向完全图 $p(T)=G$，其中 $\forall x,y\in [1,n]$，$G$ 中边 $(x,y)$ 的边权为 $dis(x,y)$。
定义 $f(T)$ 为 $p(T)$ 的最大生成树。特别的，若 $p(T)$ 的最大生成树不唯一，请立刻判断出并报告。
给定树 $T_0$ 和整数 $k$，求 $f^k(T_0)$ 。边权为正整数。
若 $\exists x\in[0,k-1]$ 使得 $p(f^x(T_0))$ 的最大生成树不唯一，输出 $-1$。否则，输出 $f^k(T_0)$ 的所有边权和对 $2^{32}$ 取模的结果。
$n\le 10^6$ ，$1\le k\le 10^7$。
Solution
赛时被 $-1$ 搞死，如果是 OI 赛制建议保证没有 $-1$。
先不考虑 $-1$ 的情况。
首先看部分分， 考虑 $k=1$ 的情况。
显然最大生成树中必然包含原树的直径，于是我们考虑跟直径有关的做法。
先求出一条直径的两条端点，然后其它点都向离它距离远的端点连边，我们便构造出了一组合法最优解。
对于 $k>1$, 我们发现做完第一次后整棵树可以看成两个端点下面挂着一堆点，然后两个端点之间连一条长度为直径的边。用队列维护一下两个部分连向父亲的值，再维护 $tag$ 标记即可。
再来看 $-1$ 的情况。
- 直径唯一。如果 $k=1$，只要看是否存在一个节点到两个端点距离相同即可，$k>1$时在模拟的过程中判断队列的前两个数是否相同，但时由于有取模，我们只能在一开始的初始值时判断
- 直径不唯一。如果所有直径都有相同的端点，并且满足直径唯一时的性质才可能有唯一解，再讨论一下即可。
具体实现看代码。
Code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define uint unsigned int
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 1e6 + 10;
int n, k, s, t;
int tot, head[N], ver[N<<1], Next[N<<1], edge[N<<1];
inline void add_edge(int u, int v, int w) {ver[++tot] = v; edge[tot] = w; Next[tot] = head[u]; head[u] = tot;}
LL mx, dep[N][2], d;
inline void dfs(int u, int fa, int p) {
if (!fa) dep[u][p] = 0;
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i], w = edge[i]; if (v == fa) continue;
dep[v][p] = dep[u][p] + w; dfs(v, u, p);
}
}
vector<LL> s1, s2;
queue<uint> q1, q2;
uint tag1, tag2, D, ans;
inline bool cmp(LL x, LL y) {return x > y;}
int main () {
n = read(); k = read();
for (int i = 2; i <= n; ++ i) {
int f = i - read(), w = read();
add_edge(f, i, w); add_edge(i, f, w);
}
dfs(1, 0, 0); // 第一次 dp 找最远点
for (int i = 1; i <= n; ++ i)
if (dep[i][0] > mx) mx = dep[i][0], s = i;
dfs(s, 0, 0);
for (int i = 1; i <= n; ++ i)
if (dep[i][0] > d) d = dep[i][0], t = i;
dfs(t, 0, 1); // s 和 t 为其中一条直径
bool flag1 = 0, flag2 = 0;
for (int i = 1; i <= n; ++ i) {
if (i == s || i == t) continue;
if (dep[i][0] == dep[t][0]) flag1 = 1; // 还有以 s 为端点的直径
if (dep[i][1] == dep[s][1]) flag2 = 1; // 还有以 t 为端点的直径
}
if (flag1 && flag2 || (flag1 || flag2) && k > 1) return puts("-1"), 0;
if (flag1) {
for (int i = 1; i <= n; ++ i) {
if (i == s || i == t) continue;
if (dep[i][0] < dep[i][1]) return puts("-1"), 0;
}
}
if (flag2) {
for (int i = 1; i <= n; ++ i) {
if (i == s || i == t) continue;
if(dep[i][1] < dep[i][0]) return puts("-1"), 0;
}
}
for (int i = 1; i <= n; ++ i) {
if (i == s || i == t) continue;
if (dep[i][0] == dep[i][1]) return puts("-1"), 0;
if (dep[i][0] > dep[i][1]) s1.push_back(dep[i][0]);
else s2.push_back(dep[i][1]);
}
sort(s1.begin(), s1.end(), cmp); sort(s2.begin(), s2.end(), cmp);
int siz1 = s1.size(), siz2 = s2.size();
for (int i = 0; i + 1 < siz1 && i < min(siz1, k-1); ++ i)
if (s1[i] == s1[i+1]) return puts("-1"), 0;
for (int i = 0; i + 1 < siz2 && i < min(siz2, k-1); ++ i)
if (s2[i] == s2[i+1]) return puts("-1"), 0;
for (auto v : s1) q1.push((uint)v);
for (auto v : s2) q2.push((uint)v);
D = d;
for (int i = 2; i <= k; ++ i) {
uint x = 0, y = 0;
flag1 = flag2 = 0;
if (!q1.empty()) x = q1.front() + tag1, q1.pop(), flag1 = 1;
if (!q2.empty()) y = q2.front() + tag2, q2.pop(), flag2 = 1;
if (flag1) q1.push(-tag1), tag1 += y + D;
if (flag2) q2.push(-tag2), tag2 += x + D;
D += x + y;
}
while (!q1.empty()) ans += q1.front() + tag1, q1.pop();
while (!q2.empty()) ans += q2.front() + tag2, q2.pop();
ans += D; printf("%u\n", ans);
return 0;
}
View Code
标签：P8934,R7,int,s2,s1,dep,TSM,端点,直径 From： https://www.cnblogs.com/CikL1099/p/17039619.html