看了下题解,用贪心写的。动规真心不会。贪心还凑和。
参见题解:https://waautomaton.blog.luogu.org/solution-p2279
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include<iostream> #include<vector> #include<queue> #include<cstring> using namespace std; int n; vector<int> edges[1005]; int depth[1005],father[1005],grandfather[1005]; struct node{ int i,dep; node(int ii,int depp){i=ii;dep=depp;} bool operator < (const node& n2) const{ return dep<n2.dep; } }; priority_queue<node> pq; bool visited[1005]; void dfsRange2(int pos,int dep){ //为什么这里不能发现visited之后就return呢,是因为有可能一个点虽被visited,但其周围的点未被扩展完全,所以其实visited在这里面没有任何作用,如果把注释去掉是20分的。 //if(visited[pos])return; visited[pos]=true; if(dep==2)return; for(int i=0;i<edges[pos].size();i++){ //if(visited[edges[pos][i]])continue; dfsRange2(edges[pos][i],dep+1); } } void dfsAll(int pos,int f,int gf,int dep){ if(visited[pos])return; visited[pos]=true; father[pos]=f; grandfather[pos]=gf; depth[pos]=dep; for(int i=0;i<edges[pos].size();i++){ if(visited[edges[pos][i]])continue; dfsAll(edges[pos][i],pos,f,dep+1); } } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=2;i<=n;i++){ int v; cin>>v; edges[i].push_back(v); edges[v].push_back(i); } memset(visited,false,sizeof(visited)); dfsAll(1,1,1,1); memset(visited,false,sizeof(visited)); for(int i=1;i<=n;i++)pq.push(node(i,depth[i])); int cnter=0; while(!pq.empty()){ if(visited[pq.top().i]){ pq.pop(); continue; } node cur=pq.top();pq.pop(); dfsRange2(grandfather[cur.i],0); cnter++; } cout<<cnter; } |