传送门
思路：
给每个入度为零的点一些流量，其流量等于该点的出度值。然后拓扑排序，如果某个点的流量等于全部流量，即为答案点(除起点)。 因为题目给的是一颗树，所以不用考虑流量分流后在聚集到一点上。也就是说，除入度为零的点以外，出度大于1的点及其后面的点都不会是答案。
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> piir; typedef long long ll; const int maxn = 1e5+5; const int INF = 0x3f3f3f3f; vector<int> G[maxn]; int in[maxn],flow[maxn],out[maxn]; int n,all; queue<int> q; void top(){ all = 0; for(int i=1;i<=n;i++){ if(in[i]==0){ in[i]=-1; q.push(i); flow[i]=G[i].size(); all += flow[i]; } } while(!q.empty()){ int u=q.front();q.pop(); for(auto v : G[u]){ if(out[u]<=1) flow[v] += flow[u]; in[v]--; if(in[v]==0) q.push(v); } } } int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); for(int u,v,i=1;i<n;i++){ scanf("%d%d",&u,&v); G[u].push_back(v); in[v]++; out[u]++; } top(); for(int i=1;i<=n;i++){ if(flow[i]==all && in[i]!=-1) printf("%d\n",i); } return 0; }
