1 条题解
-
0
显然,我们可以先预处理从一号节点到所有叶子的最短路,然后我们在所有最短路中先走路程短的,再走路程长的,我们在走的时候我们要注意标记即可。
Code:
#include<bits/stdc++.h> #define int long long #define I_love_ch ios::sync_with_stdio(0) #define China cin.tie(0) #define France cout.tie(0) #define ch_France return 0 #define Nyacode main using namespace std; struct node{ int ans,id; friend bool operator < (node x,node y){ return x.ans>y.ans; } }; struct leaf{ int id,dis; }lf[200010]; bool cmp(leaf x,leaf y){ return x.dis<y.dis; } int n,x,dis[200010],deg[200010]; vector<int> g[200010]; bool vis[200010]; priority_queue<node> q; void dijkstra(){ for(int i=1;i<=n;i++){ dis[i]=1e9; } dis[1]=0; q.push((node){0,1}); while(!q.empty()){ node t=q.top(); q.pop(); int u=t.id; if(vis[u]) continue; vis[u]=1; for(auto v:g[u]){ if(dis[v]>dis[u]+1){ dis[v]=dis[u]+1; if(!vis[v]) q.push((node){dis[v],v}); } } } } int fa[200010]; void dfs_find_fa(int u,int father){ for(auto v:g[u]){ if(v==father) continue; dfs_find_fa(v,u); fa[v]=u; } } int now=0; void dfs(int u){ if(fa[u]==0) return; if(!vis[u]){ vis[u]=1; now++; } dfs(fa[u]); } signed Nyacode(){ freopen("altra.in","r",stdin); freopen("altra.out","w",stdout); I_love_ch; China; France; cin>>n; for(int i=1;i<n;i++){ cin>>x; g[x].push_back(i+1); g[i+1].push_back(x); deg[i+1]++; deg[x]++; } dijkstra(); int len=0; for(int i=1;i<=n;i++){ if(deg[i]==1&&i!=1){ len++; lf[len].dis=dis[i]; lf[len].id=i; } } sort(lf+1,lf+len+1,cmp); fa[1]=0; dfs_find_fa(1,0); int maxx=0,minn=1e9; memset(vis,0,sizeof(vis)); for(int i=1;i<=len;i++){ now=0; dfs(lf[i].id); minn=min(minn,now); maxx=max(maxx,now); } cout<<maxx-minn<<"\n"; ch_France; }
- 1
信息
- ID
- 971
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 26
- 已通过
- 8
- 上传者