A.dist
Statement:
给定一棵 \(n(n \le 10^6)\) 个节点带边权的树，定义 \(\mathrm{Min}(x, y)\) 是 \((x, y)\) 路径上的边权最小值。求 \(\max_{r = 1}^n {\sum_{v \ne i} \mathrm{Min}(r, v)}\)。
Solution:
经典套路题。
首先注意到一条路径上的只有最小值才会产生贡献，于是对于一个连通块，我们找到最小的那个边，并分成两个连通块 \(\mathrm{A, B}\)，假如把根放在 \(\mathrm A\) 中，那么对于连通块 \(\mathrm B\) 到根的所有路径贡献都是这个最小边的边权，然后递归计算 \(\mathrm A\) 的贡献，对于放在 \(\mathrm B\) 中的情况一样做即可。但是这样的时间复杂度是 \(O(n^2)\) 的。
于是将删边改成加边，具体的，我们将边按边权从大到小排序，每次合并两个集合，用个并查集维护即可。时间复杂度 \(O(n \log n)\)。
qwq
#include<bits/stdc++.h>
#pragma GCC optimize(3, "Ofast", "inline")
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, fa[N], siz[N], val[N];
struct Edge{
int u, v, w;
}E[N];
bool cmp(struct Edge E1, struct Edge E2){
return E1.w > E2.w;
}
int findfa(int x){return fa[x] = (fa[x] == x) ? x : findfa(fa[x]);}
void merge(int x, int y, int w){
int fx = findfa(x), fy = findfa(y);
if(fx == fy) return; if(siz[fx] < siz[fy]) swap(fx, fy);
val[fx] = max(val[fx] + siz[fy] * w, val[fy] + siz[fx] * w);
fa[fy] = fx; siz[fx] += siz[fy];
}
signed main(){
// freopen("dist3.in", "r", stdin);
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n; for(int i = 1; i <= n; i++) siz[i] = 1, fa[i] = i;
for(int i = 1; i < n; i++) cin >> E[i].u >> E[i].v >> E[i].w;
sort(E + 1, E + n, cmp);
for(int i = 1; i < n; i++) merge(E[i].u, E[i].v, E[i].w);
cout << val[findfa(1)];
return 0;
}
B.wolf
Statement:
有 \(n(1 \le n \le 3000)\) 间屋子，由 \(n − 1\) 条双向道路连接成了一个树形结构。其中，第 \(i\) 间屋子里居住了 \(1\) 个种族为 \(c_i\) 的狼人。现在你要召集一个连通块内的狼人。设 \(a_j\) 表示被召集的种族为 \(j\) 的狼人个数，若存在 \(2 a_k > \sum a_j\) ，则种族为 \(k\) 的狼人会造反。你想知道有多少个连通块会使某种狼人造反，答案对 \(998244353\) 取模。
Solution:
首先对判定进行转化：\(2a_k > \sum_{j = 1}^n a_j \Leftrightarrow a_k - \sum_{j \ne k} a_j > 0\)。
所以可以枚举作为众数的种类然后做一遍做一遍树上背包，这样时间复杂度是 \(O(n^3)\)。然后注意到对于一个总共有 \(cnt_i\) 个狼人的种类 \(i\)，背包上下限是 \(cnt_i\)，由树上背包的时间复杂度做一次是 \(O(ncnt_i)\) 的，于是总复杂度是 \(O(n^2)\) 的了。
qwq
#include<bits/stdc++.h>
#pragma GCC optimize(3, "Ofast", "inline")
#define int long long
using namespace std;
const int N = 3000 + 10, mod = 998244353;
int n, m, col[N], _col[N], f[N][2 * N], cnt0[N], cnt1[N], ans, tmp[2 * N];
struct edge{
int v, next;
}edges[N << 1];
int head[N], idx;
int id(int val){if(val < 0) val += 2 * m + 1; return val;}
void ADD(int& x, int y){x = (x + y) % mod;}
void add_edge(int u, int v){
edges[++idx] = {v, head[u]};
head[u] = idx;
}
int mymax(int x, int y){return (x > y) ? x : y;}
void dfs(int u, int fa){
cnt0[u] = (!col[u]); cnt1[u] = col[u]; //f[u][0] = 1;
for(int i = -m; i <= m; i++) f[u][id(i)] = 0;
f[u][(cnt0[u] ? id(-1) : 1)] = 1;
// cout << u << " " << f[u][id(-1)] << " " << f[u][1] << "\n";
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(v == fa) continue;
dfs(v, u);
for(int i = mymax(-m, -cnt0[u]); i <= cnt1[u]; i++) tmp[id(i)] = f[u][id(i)];
for(int i = mymax(-m, -cnt0[u]); i <= cnt1[u]; i++){
for(int j = mymax(-m, -cnt0[v]); j <= cnt1[v]; j++){
if(i + j >= -m && i + j <= m) ADD(f[u][id(i + j)], tmp[id(i)] * f[v][id(j)] % mod);
}
}
cnt1[u] += cnt1[v]; cnt0[u] += cnt0[v];
}
// for(int i = mymax(-m, -cnt0[u]); i <= cnt1[u]; i++) cout << u << " " << i << " " << f[u][id(i)] << "\n";
for(int i = 1; i <= cnt1[u]; i++) ADD(ans, f[u][i]);
}
signed main(){
// freopen("wolf6.in", "r", stdin);
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n; for(int i = 1; i <= n; i++) cin >> _col[i];
for(int i = 1; i < n; i++){
int x, y; cin >> x >> y;
add_edge(x, y); add_edge(y, x);
}
for(int tcol = 1; tcol <= n; tcol++){
m = 0;
for(int i = 1; i <= n; i++) col[i] = (_col[i] == tcol), m += col[i];
if(m) dfs(1, 0);
}
cout << ans;
return 0;
}