当出现形如「每个结点最多与 \(k\) 条边相连」且 \(k\) 很小的时候,可以考虑树形DP+状压合并子树
基于一个挺套路的结论:
- 就题论题,这个题合并子树如果是状压枚举选哪些边的话只能过 \(n=5\)
但如果压选择了哪些与根节点直接相连的边被选,对于每个状态枚举所有路径,如果两个端点所在子树都没被选过就转移则可以过 \(n=15\) 或更高
Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 1010
#define ll long long
#define reg register int
#define fir first
#define sec second
#define make make_pair
#define pb push_back
//#define int long long
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}
int n, m;
int head[N], size;
struct edge{int to, next, id;}e[N<<1];
inline void add(int s, int t, int i) {e[++size].to=t; e[size].id=i; e[size].next=head[s]; head[s]=size;}
namespace force{
pair<int, int> q[N];
bitset<1500> lim[10000];
bool dfs(int u, int to, int fa, bitset<1500>& dat) {
if (u==to) return 1;
for (int i=head[u],v; ~i; i=e[i].next) {
v = e[i].to;
if (v!=fa && dfs(v, to, u, dat)) {dat[e[i].id]=1; return 1;}
}
return 0;
}
void solve() {
for (int i=1,u,v; i<n; ++i) {
u=read(); v=read();
add(u, v, i); add(v, u, i);
}
m=read();
for (int i=1; i<=m; ++i) {
q[i].fir=read(); q[i].sec=read();
dfs(q[i].fir, q[i].sec, 0, lim[i]);
}
int lim2=1<<m, ans=0;
bitset<1500> used;
for (int s=1,s2,cnt; s<lim2; ++s) {
s2=s; cnt=0;
do {++cnt; s2&=s2-1;} while (s2);
if (cnt<=ans) goto jump;
used.reset();
for (int i=0; i<m; ++i) if (s&(1<<i)) {
if ((used&lim[i+1]).any()) goto jump;
else used|=lim[i+1];
}
ans=cnt;
jump: ;
}
printf("%d\n", ans);
exit(0);
}
}
namespace task1{
int ans, lst;
struct line{int l, r; inline void build(int a, int b) {l=a; r=b;}}p[N];
inline bool operator < (line a, line b) {return a.r==b.r?a.l<b.l:a.r<b.r;}
void solve() {
for (int i=1,u,v; i<n; ++i) {
u=read(); v=read();
add(u, v, i); add(v, u, i);
}
m=read();
for (int i=1,u,v; i<=m; ++i) {
u=read(); v=read();
if (u>v) swap(u, v);
p[i].build(u, v);
}
sort(p+1, p+m+1);
++ans, lst=p[1].r;
for (int i=2; i<=m; ++i) {
if (p[i].l>=lst) ++ans, lst=p[i].r;
}
printf("%d\n", ans);
exit(0);
}
}
namespace task{
int dp[N], rk[N], f[1<<11], top, e2[N];
vector<int> e[N], son[N];
pair<int, int> path[N*N];
bool q[N][N], lock[12];
void dfs(int u, int fa) {
// cout<<"dfs: "<<u<<' '<<fa<<endl;
son[u].pb(u);
for (auto v:e[u]) if (v!=fa) dfs(v, u);
int tot=0, top=0;
memset(lock, 0, sizeof(lock));
for (auto v:e[u]) if (v!=fa) {
rk[v]=tot; e2[tot++]=v;
dp[u]+=dp[v];
for (auto i:son[v]) {
// cout<<"i: "<<i<<endl;
if (q[i][u]) {
lock[tot-1]=1;
break;
}
for (int j=0; j<tot-1; ++j)
for (auto k:son[e2[j]]) {
// cout<<"k: "<<k<<endl;
if (q[i][k]) {
path[++top]=make(tot-1, j);
break;
}
}
}
}
// cout<<"top: "<<top<<endl;
// cout<<"tot: "<<tot<<endl;
int lim=1<<tot, must=lim-1, maxn=0;
memset(f, 0, sizeof(f));
for (int s=0; s<lim; ++s) {
maxn=max(maxn, f[s]);
for (int i=0; i<tot; ++i) if (lock[i] && !(s&(1<<i))) f[s|(1<<i)]=max(f[s|(1<<i)], f[s]+1); //, cout<<1<<endl;
for (int i=1; i<=top; ++i) {
if (!(s&(1<<path[i].fir)) && !(s&(1<<path[i].sec)))
f[s|(1<<path[i].fir)|(1<<path[i].sec)] = max(f[s|(1<<path[i].fir)|(1<<path[i].sec)], f[s]+1); //, cout<<2<<' '<<bitset<5>(s|(1<<path[i].fir)|(1<<path[i].sec))<<endl;
}
}
if (maxn) {for (int s=1; s<lim; ++s) if (f[s]==maxn) must&=s;}
else must=0;
// cout<<"u: "<<u<<endl;
// cout<<"maxn: "<<maxn<<endl;
// cout<<"must: "<<must<<endl;
dp[u]+=maxn;
// cout<<"son: "; for (auto it:son[u]) cout<<it<<' '; cout<<endl;
for (int i=0; i<tot; ++i) if (!(must&(1<<i))) {
// cout<<"add: "<<i<<' '<<e2[i]<<endl;
for (auto j:son[e2[i]]) son[u].pb(j);
}
// cout<<"son: "; for (auto it:son[u]) cout<<it<<' '; cout<<endl;
}
void solve() {
for (int i=1,u,v; i<n; ++i) {
u=read(); v=read();
e[u].pb(v); e[v].pb(u);
}
m=read();
for (int i=1,u,v; i<=m; ++i) {
u=read(); v=read();
q[u][v]=q[v][u]=1;
}
dfs(1, 0);
printf("%d\n", dp[1]);
exit(0);
}
}
signed main()
{
freopen("select.in", "r", stdin);
freopen("select.out", "w", stdout);
memset(head, -1, sizeof(head));
n=read();
// if (n<=5) force::solve();
// else task1::solve();
task::solve();
return 0;
}