线段树实在写不下去了来写一下拓扑序吧。模版参见某谷B3644大意给出每个人的后代的信息。输出一个序列使得每个人的后辈都比那个人后列出。思路这玩意儿有点简单这个家族的关系很显然可以用有向图来表示。假设边的方向是由祖先指向后辈那么后辈一定会有入度。在图论中顶点的度(d e g r e e degreedegree)是指与该顶点相连的边的数量指向该顶点的边数即为入度。所以每次只需要找到入度为0的点将其加入答案中并将其后辈的入度-1如此循环即可。数据结构上可以用队列存入度为0的点。代码#includebits/stdc.husingnamespacestd;#defineN103intn,into[N];queueintq;vectorintans;vectorintg[N];intmain(){cinn;for(inti1;in;i){while(1){intx;cinx;if(x0)break;g[i].push_back(x);into[x];}}for(inti1;in;i)if(into[i]0)q.push(i);while(!q.empty()){intuq.front();q.pop();ans.push_back(u);for(intv:g[u]){into[v]--;if(into[v]0)q.push(v);}}for(inta:ans)couta ;return0;}小试牛刀P4017题外话一看到生物想到自己地生会考的成绩就闹心ε(´ο*)))题目大意就是找食物网中最大食物链(即从生产者到最高级消费者)的数量。思路很显然是DP(万物皆可DP)。状态d p [ u ] dp[u]dp[u]表示强制以u uu结尾的食物链的条数。根据生物知识食物链的方向由低到高。如果u uu的捕食者是v vv那么所有指向u uu的食物链都会指向v vv。将食物网建成有向图拓扑排序后v vv就一定在u uu的后面。转移在拓扑排序的基础上对于所有入度为0的点向外拓展并将自己的d p dpdp值加到它的捕食者上。答案将所有出度为0(最高级消费者)的点的d p dpdp值相加即可。初始化将所有入度为0(生产者)的点初始化为1其余为0。代码#includebits/stdc.husingnamespacestd;#defineN5001#definemod80112002intn,m,dp[N],into[N],out[N];vectorintg[N];queueintq;intmain(){cinnm;for(inti1;im;i){intu,v;cinuv;g[u].push_back(v);into[v];out[u];}for(inti1;in;i){if(into[i]0){dp[i]1;q.push(i);}}while(!q.empty()){intuq.front();q.pop();for(intv:g[u]){into[v]--;if(into[v]0)q.push(v);dp[v](dp[v]dp[u])%mod;}}intans0;for(inti1;in;i)if(out[i]0)ans(ansdp[i])%mod;coutans;return0;}—————————————————————— T h e E n d —————————————————————— ——————————————————————The\ \ End————————————————————————————————————————————TheEnd——————————————————————