各种dfs
按照LRJ书上的思路写就行了
#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<stack>#include<set>#include<queue>#include<vector>using namespace std;const int maxn = 1111;vector<int>G[maxn];set<int>is_node;int n,s,k;int fa[maxn];int vis[maxn];int have[maxn];struct Node{int id;int dep;Node(int i = 0,int d = 0):id(i),dep(d){};friend bool operator < (Node a,Node b){return a.dep > b.dep;}};vector<Node>node;void dfs_node(int u,int dep,int f){int le = 0;vis[u] = 1;fa[u] = f;for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(!vis[v]){dfs_node(v,dep + 1,u);le = 1;}}if(!le){node.push_back(Node(u,dep));is_node.insert(u);}return;}void debug(){for(int i = 0; i < node.size(); i++)printf("%d %d\n",node[i].id,node[i].dep);}void dfs_solve(int u,int d){if(d == k)return;for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(!vis[v]){if(is_node.count(v))have[v] = 1;elsedfs_solve(v,d + 1);}}return;}int judge(){int e = 0;for(int i = 0; i < node.size(); i++)if(!have[node[i].id]){e = node[i].id;break;}if(!e) return 0;int d = 0;while(fa[e] != -1 && d < k){e = fa[e];d ++;}return e;}int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d%d",&n,&s,&k);for(int i = 1; i <= n; i++) G[i].clear();node.clear();is_node.clear();memset(vis,0,sizeof(vis));memset(have,0,sizeof(have));for(int i = 0; i < n – 1; i++){int a,b;scanf("%d%d",&a,&b);G[a].push_back(b);G[b].push_back(a);}dfs_node(s,0,-1);sort(node.begin(),node.end());int serve = s;int ans = 0;do{memset(vis,0,sizeof(vis));dfs_solve(s,0);s = judge();if(!s) break;ans ++;}while(true);printf("%d\n",ans);}return 0;}
，我们可以冷静理智的给这些刺一一贴上标签:骄傲，自负，脆弱的自尊心，
