题解 P3942 【将军令】

zhoujun · 2017-11-04 15:12:39 · 题解

dfs1的作用是把节点1作为根节点（深度记为1）计算所有点的深度。

然后按深度给序号排序。

dfs2是从当前还未被覆盖深度最大的节点，查所有2k步之内的节点并做标记（从最深的节点走k步的节点驻扎一小队正好可以覆盖最深的节点，而从这一节点再走k步就是走该节点可以覆盖的所有节点。即从最深的节点走2k步）。

每走一次dfs2答案加1。

#include<algorithm>
#include<iostream>
#include<vector> 
using namespace std;
int n, k, t, d[100005], ans;
bool z[100005], s[100005];
pair<int,int> p[100005];
vector<int> v[100005];
void dfs1(int x,int deep){//x为当前节点，deep为深度
    d[x]=deep;
    for(int i=0; i<v[x].size(); i++){
        if(d[v[x][i]]==0){
            dfs1(v[x][i],deep+1);
        }
    }
}
void dfs2(int x,int deep){
    s[x]=1;z[x]=1;
    for(int i=0; i<v[x].size(); i++){
        if(!s[v[x][i]]&&deep>0){
            dfs2(v[x][i],deep-1);
        }
    }
    s[x]=0;
}
int main(){
    int i, x, y;
    cin >> n >> k >> t;
    for(i=1; i<n; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(1,1);
    for(i=1; i<=n; i++) p[i].first=-d[i],p[i].second=i;//为了让sort排序后是按深度从大到小，p[i].first取深度的复数（懒）
    sort(p+1,p+n+1);
    for(i=1; i<=n; i++){
        if(!z[p[i].second]){//如果节点z[p[i].second]没有被覆盖过
            dfs2(p[i].second,2*k);//从p[i].second开始走2k步
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}