- 直径
- 点覆盖集
- 路径覆盖
- 支配集
难度：2
前提：动态规划
后继：
资料：
-
https://cses.fi/problemset/task/1133
#include <lastweapon/io> using namespace lastweapon; const int N = int(2e5) + 9; int n, h[N]; LL f[N], g[N]; VVI v; void dfs1(int r, int p = -1) { for(int& a : v[r]) if (a != p) { dfs1(a, r); h[r] += h[a]; f[r] += f[a] + h[a]; } h[r]++; } void dfs2(int r, int p = -1) { for(int& a : v[r]) if (a != p) { g[a] = (f[r] - (f[a] + h[a])) + g[r] + (n - h[a]); dfs2(a, r); } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif RD(n); v.resize(n); int a, b; while(cin >> a >> b) { v[a-1].PB(b-1); v[b-1].PB(a-1); } dfs1(0); dfs2(0); REP(i, n) printf("%lld ", f[i] + g[i]); } -
https://usaco.guide/problems/ac-subtree/solution
#include <lastweapon/io> #include <lastweapon/number> using namespace lastweapon; const int N = int(1e5) + 9; VI adj[N]; Int f[N], fl[N], fr[N], g[N]; int n; void dfs1(int u = 0, int p = -1) { f[u] = 1; for(auto& v: adj[u]) if (v != p) { dfs1(v, u); fl[v] = f[u]; f[u] *= f[v] + 1; } f[u] = 1; for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) { int v = *it; if (v == p) continue; fr[v] = f[u]; f[u] *= f[v] + 1; } } void dfs2(int u = 0, int p = -1) { for(auto& v: adj[u]) if (v != p) { g[v] = (g[u] + 1) * fl[v] * fr[v]; //f[u] / (f[v] + 1); dfs2(v, u); } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif RD(n, MOD); DO(n - 1) { int a, b; RD(a, b); --a; --b; adj[a].PB(b); adj[b].PB(a); } dfs1(); dfs2(); REP(i, n) printf("%d\n", f[i] * (g[i] + 1)); } -
https://codeforces.com/contest/1187/problem/E
