1 条题解

  • 0
    @ 2026-11-7 15:21:47

    显然,我们可以先预处理从一号节点到所有叶子的最短路,然后我们在所有最短路中先走路程短的,再走路程长的,我们在走的时候我们要注意标记即可。

    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

    [2026济南登峰营] D3 P2 唉舞萌痴(altra) - 文件读写

    信息

    ID
    971
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    26
    已通过
    8
    上传者