小明要去一个国家旅游。这个国家有#NN个城市，编号为11至NN，并且有MM条道路连接着，小明准备从其中一个城市出发，并只往东走到城市i停止。
所以他就需要选择最先到达的城市，并制定一条路线以城市i为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。
现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的i，都需要你为小明制定一条路线，并求出以城市ii为终点最多能够游览多少个城市。
第11行为两个正整数N, MN,M。
接下来MM行，每行两个正整数x, yx,y，表示了有一条连接城市xx与城市yy的道路，保证了城市xx在城市yy西面。
NN行，第ii行包含一个正整数，表示以第ii个城市为终点最多能游览多少个城市。
5 6 1 2 1 3 2 3 2 4 3 4 2 5
1 2 3 4 3
均选择从城市1出发可以得到以上答案。
对于20\%20%的数据，N ≤ 100N≤100；
对于60\%60%的数据，N ≤ 1000N≤1000；
对于100\%100%的数据，N ≤ 100000,M ≤ 200000N≤100000,M≤200000。
反向存图，那么问题就转化成了 从第 i 个点出发，所有走的最大距离
dp[i] 表示经过第 i 条边所能走的最大距离，利用这一点剪枝，效率是很高的。每一个点都dfs一边求答案
Code：
#include<bits/stdc++.h> #define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl #define pii pair<int,int> #define clr(a,b) memset((a),b,sizeof(a)) #define rep(i,a,b) for(int i = a;i < b;i ++) #define pb push_back #define MP make_pair #define LL long long #define ull unsigned LL #define ls i << 1 #define rs (i << 1) + 1 #define fi first #define se second #define ptch putchar #define CLR(a) while(!(a).empty()) a.pop() using namespace std; inline LL read() { LL s = 0,w = 1; char ch = getchar(); while(!isdigit(ch)) { if(ch == ‘-‘) w = -1; ch = getchar(); } while(isdigit(ch)) s = s * 10 + ch - ‘0‘,ch = getchar(); return s * w; } inline void write(LL x) { if(x < 0) putchar(‘-‘), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + ‘0‘); } const int maxn = 1e5 + 10; int head[maxn],cnt; struct xx{ int v,nex; xx(int v = 0,int nex = 0): v(v),nex(nex){} }edge[maxn << 1]; int dp[maxn << 1]; int dfs(int p,int f){ int ans = 0; for(int i = head[p]; ~i;i = edge[i].nex){ int v = edge[i].v; if(v == f) continue; if(!dp[i]) dp[i] = dfs(v,p) + 1; ans = max(ans,dp[i]); } return ans; } int main() { //#ifndef ONLINE_JUDGE // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); //#endif int n = read(),m = read(); clr(head,-1); cnt = 0; for(int i = 1;i <= m;++ i){ int u = read(),v = read(); edge[cnt] = xx(u,head[v]); head[v] = cnt ++; } for(int i = 1;i <= n;++ i) write(dfs(i,-1) + 1),ptch(‘\n‘); return 0; }
原文：https://www.cnblogs.com/rookie-acmer/p/11354464.html