这道题显然是一个树上问题，题目让我们求到各个点得逆序边最小的点是哪些
我们对于树形dp，一般来说都有一个边上的权值，那么对于本题，我们就要对题目信息进行转化
所以我们不妨把正向边记作0，逆向边记作1，这样我们就能够通过一次dfs来计算到子树中的各个节点需要多少次逆转
我们可以随便挑1作为根节点
那么剩下的问题也比较清晰，既然知道了子树，只需知道往上的次数是多少，往上的次数无非就是父节点减去我这颗子树的答案
这样就是你的父亲节点到其他点的次数了，相加就是答案
这里还有一个小细节就是第二次dfs你和父亲节点相连的这条边的权值考虑
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+10; const int mod=1e9+7; int f[N]; int ne[N],e[N],idx,w[N],h[N]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void dfs1(int u,int fa){ int i; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa) continue; dfs1(j,u); f[u]+=f[j]+w[i]; } } void dfs2(int u,int fa){ int i; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa) continue; f[j]+=(f[u]-f[j])+(w[i]?-1:1); dfs2(j,u); } } int main(){ int n; int i; cin>>n; memset(h,-1,sizeof h); for(i=1;i<n;i++){ int a,b; scanf("%d%d",&a,&b); add(a,b,0); add(b,a,1); } dfs1(1,0); dfs2(1,0); int ans=n-1; for(i=1;i<=n;i++) ans=min(ans,f[i]); vector<int> num; for(i=1;i<=n;i++){ if(f[i]==ans) num.push_back(i); } cout<<ans<<endl; for(auto x:num){ printf("%d ",x); } cout<<endl; }