BZOJ5072:[Lydsy1710月赛]小A的树(树形DP)

Description

BZOJ只是扔了个下载链接

Solution

设$f[x][i]$表示$x$点选中$i$个黑点的最小连通块。

设$g[x][i]$表示$x$点选中$i$个黑点的最大连通块。

转移非常明显。处理出每个情况的上下界之后差分一下$O(1)$回答询问即可。

卡空间所以要用$short$。第二次$INF$开大了……应该多上点心了……

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (5009) 
 5 using namespace std;
 6 
 7 struct Edge{int to,next;}edge[N<<1];
 8 int n,u,v,T,q,INF=1e4,size[N],b[N];
 9 short f[N][N],g[N][N],tmpf[N],tmpg[N],ans[N][N];
10 int head[N],num_edge;
11 
12 void add(int u,int v)
13 {
14     edge[++num_edge].to=v;
15     edge[num_edge].next=head[u];
16     head[u]=num_edge;
17 }
18 
19 void Dfs(int x,int fa)
20 {
21     size[x]=1;
22     for (int i=0; i<=n; ++i)
23         f[x][i]=INF,g[x][i]=-INF;
24     f[x][b[x]]=g[x][b[x]]=1;
25     for (int i=head[x]; i; i=edge[i].next)
26         if (edge[i].to!=fa)
27         {
28             int to=edge[i].to;
29             Dfs(to,x);
30             for (int j=0; j<=size[x]+size[to]; ++j)
31                 tmpf[j]=INF,tmpg[j]=-INF;
32             for (int j=0; j<=size[x]; ++j)
33                 for (int k=0; k<=size[to]; ++k)
34                 {
35                     tmpf[j+k]=min((int)tmpf[j+k],(int)f[x][j]+f[to][k]);
36                     tmpg[j+k]=max((int)tmpg[j+k],(int)g[x][j]+g[to][k]);
37                 }
38             size[x]+=size[to];
39             for (int j=0; j<=size[x]; ++j)
40             {
41                 f[x][j]=min(f[x][j],tmpf[j]);
42                 g[x][j]=max(g[x][j],tmpg[j]);
43             }
44         }
45     for (int i=0; i<=size[x]; ++i)
46         if (f[x][i]<INF)
47             ans[f[x][i]][i]++,ans[g[x][i]+1][i]--;
48 }
49 
50 int main()
51 {
52     scanf("%d",&T);
53     while (T--)
54     {
55         memset(ans,0,sizeof(ans));
56         memset(head,0,sizeof(head));
57         num_edge=0;
58         scanf("%d%d",&n,&q);
59         for (int i=1; i<=n-1; ++i)
60             scanf("%d%d",&u,&v),add(u,v),add(v,u);
61         for (int i=1; i<=n; ++i)
62             scanf("%d",&b[i]);
63         Dfs(1,0);
64         for (int i=1; i<=n; ++i)
65             for (int j=0; j<=n; ++j)
66                 ans[i][j]+=ans[i-1][j];
67         for (int i=1; i<=q; ++i)
68         {
69             scanf("%d%d",&u,&v);
70             if (ans[u][v]) puts("YES");
71             else puts("NO");
72         }
73         puts("");
74     }
75 }