51Nod 1378 夹克老爷的愤怒

夹克老爷逢三抽一之后，由于采用了新师爷的策略，乡民们叫苦不堪，开始组织起来暴力抗租。

夹克老爷很愤怒，他决定派家丁常驻村中进行镇压。

诺德县有N个村庄，编号0 至 N-1，这些村庄之间用N - 1条道路连接起来。

家丁都是经过系统训练的暴力机器，每名家丁可以被派驻在一个村庄，并镇压当前村庄以及距离该村庄不超过K段道路的村庄。

夹克老爷一贯奉行最小成本最大利润的原则，请问要实现对全部村庄的武力控制，夹克老爷需要派出最少多少名家丁?

Input

第1行：2个数N, K中间用空格分隔(1<= N <= 100000, 0 <= K <= N)。
之后N-1行：每行2个数S, E中间用空格分隔，表示编号为S的村庄同编号为E的村庄之间有道路相连。(0 <= S, E < N)。

Output

输出一个数说明要实现对全部村庄的武力控制，夹克老爷需要派出最少多少名家丁?

Input示例

Output示例

官方题解：

树形DP，贪心思想，从叶子节点向上，能不放就不放，到了k长就放一个。

后序遍历，记录不同子树上传的状态，子树状态记录为该子树可以向上管理的（缺少的用负数）

可能A子树放置的家丁可以把B子树的村庄全部覆盖，这样就可以节约家丁数了。

min_length = min(dp[child])

max_length = max(dp[child])

if(min_length <= -K) {
++result;
dp[cur_idx] = K; //子树需要暴力支援深度达到K了，必须在当前位置放置一个家丁，并向上提供K的暴力输出
} else if(max_length + min_length > 0) {
dp[cur_idx] = max_child - 1; //有一个子树放置的家丁能够把全部其他需要镇压的村庄都覆盖
} else {
dp[cur_idx] = min_child - 1; //继续向上级要求暴力支持
}

最后如果root的状态小于0要额外多放一个。

 1 #include <cctype>
 2 #include <cstdio>
 3 #include <vector>
 4 
 5 const int INF=0x3f3f3f3f;
 6 const int MAXN=100010;
 7 
 8 int n,k,ans;
 9 
10 int dp[MAXN];
11 
12 bool vis[MAXN];
13 
14 std::vector<int> Graph[MAXN];
15 
16 inline void read(int&x) {
17     int f=1;register char c=getchar();
18     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
19     for(;isdigit(c);x=x*10+c-48,c=getchar());
20     x=x*f;
21 }
22 
23 void DFS(int num) {
24     vis[num]=true;
25     int mn=INF,mx=-INF;
26     for(int i=0;i<Graph[num].size();++i) {
27         int v=Graph[num][i];
28         if(!vis[v]) {
29             DFS(v);
30             mn=mn<dp[v]?mn:dp[v];
31             mx=mx<dp[v]?dp[v]:mx;
32         }
33     }
34     if(mn==INF) dp[num]=-1;
35     else if(mn<=-k) ++ans,dp[num]=k;
36     else if(mn+mx>0) dp[num]=mx-1;
37     else dp[num]=mn-1;
38     vis[num]=false;
39 }
40 
41 int hh() {
42     read(n);read(k);
43     if(k==0) {printf("%d
",n);return 0;}
44     for(int x,y,i=1;i<n;++i) {
45         read(x);read(y);
46         ++x;++y;
47         Graph[x].push_back(y);
48         Graph[y].push_back(x);
49     }
50     DFS(1);
51     if(dp[1]<0) ++ans;
52     printf("%d
",ans);
53     return 0;
54 }
55 
56 int sb=hh();
57 int main(int argc,char**argv) {;}

代码