我想我经大神点拨后终于明白了。。。回学校再写吧
时间限制：1s
内存限制：256MB
【问题描述】
A国是一个商业高度发达的国家。它包含了n座城市，每座城商业都很发达。但不幸的是，A国的交通并没有像其商业那么发达，它仅仅保证了任意两座城市之间有路径存在，而且只存在唯一的一条！
拥有雄厚经济实力的商人们决定集资修建一条路，但在修建方案上各个商人都希望新建成的道路对自己利益最大。最终他们决定造一条路，使得两个城市间所需经过道路的数量的最大值尽可能小。为此他们提出了很多修建方案，但他们并不知道每一方案新建道路后最远城市间的最大值为多少，他们有多种修建方案，你能告诉他们每一方案对应的最远城市间的最大值吗？
【输入】
输入文件名为road.in。
第一行两个数n，m（1<=n、m<=3,000），分别表示城市个数和方案个数
接下来n-1行，每行两个数x、y，表示有一条道路连接x号城市和y号城市
m下来m行，每行两个数a、b，表示一个修建方案对应的两个城市
【输出】
输出文件名为road.out。
对于每组数据输出一行，包含一个数，表示新建道路后，最远城市间所需经过的道路数量
【输入输出样例】
| road.in | road.out |
| 8 2 1 3 2 3 3 4 4 5 5 6 6 7 6 8 3 6 1 8 | 3 5 更正 |
【数据说明】
对于40%的数据，1<=n,m<=300；
对于另外20%的数据，数据呈一条链
对于100%的数据，1<=n,m<=3000
#include#include #include #include #include #include using namespace std;const int N=3009; int n,m;int h[N],nex[N*2],to[N*2],cnt;int f[N];bool vis[N];int dep[N],deep[N];int max_son[N];int maxn,root;void Add(int x,int y){ to[++cnt]=y,nex[cnt]=h[x],h[x]=cnt; return;}void dfs1(int x,int tot){ vis[x]=1; for(int i=h[x];i;i=nex[i]) if(!vis[to[i]]) dfs1(to[i],tot+1); if(tot>maxn) maxn=tot,root=x; return ;}int dfs2(int x,int tot,int last){ vis[x]=0;f[x]=last;dep[x]=tot; int sum=0; for(int i=h[x];i;i=nex[i]) if(vis[to[i]]) sum=max(sum,dfs2(to[i],tot+1,x)); sum=max(sum,tot); maxn=max(maxn,sum); max_son[x]=sum; return sum;}void work(int u,int v){ int t,len,ans=0; if(dep[u]>=dep[v]) t=u;else if(dep[v]>dep[u]) t=v; int minn=min(dep[v],dep[u]); ans=dep[f[t]]; ans=max(ans,(minn+1)); cout< <
#include#include #include #include #include #include using namespace std;const int N=3009; int n,m;int h[N],nex[N*2],to[N*2],cnt;int f[N];bool vis[N];int dep[N],deep[N];int max_son[N];int maxn,root;void Add(int x,int y){ to[++cnt]=y,nex[cnt]=h[x],h[x]=cnt;}void dfs1(int x,int tot){ vis[x]=1; for(int i=h[x];i;i=nex[i]) if(!vis[to[i]]) dfs1(to[i],tot+1); if(tot>maxn) maxn=tot,root=x; return ;}int dfs2(int x,int tot,int last){ vis[x]=0;f[x]=last;dep[x]=tot; int sum=0; for(int i=h[x];i;i=nex[i]) if(vis[to[i]]) sum=max(sum,dfs2(to[i],tot+1,x)); sum=max(sum,tot); maxn=max(maxn,sum); max_son[x]=sum; return sum;}void work(int u,int v){ int t,len,ans=0,last; if(dep[u]>=dep[v]) t=u;else if(dep[v]>dep[u]) t=v; int minn=min(dep[v],dep[u]); /* if(max_son[t]!=maxn) { printf("%d\n",maxn); return; }else { int ans; ans=maxn-(dep[t]-minn)+1; ans=max(ans,minn+1+(dep[t]-minn)/2); printf("%d\n",ans); return ; } */ /* len=minn+1;last=t; ans=max_son[t]-(dep[t]-minn)+1; while(dep[t]>len) { for(int i=h[t];i;i=nex[i]) if((to[i]!=f[t])&&(to[i]!=last)) { ans=max(ans,max_son[to[i]]-(dep[t]-len)); } last=t;t=f[t];len++; } */ ans=dep[f[t]]; printf("%d\n",ans); return ;}int main(){ scanf("%d%d",&n,&m); for(int i=1,x,y;i
#include#include #include #include #include #include using namespace std;const int N=3009; int n,m;int h[N],nex[N*2],to[N*2],cnt;int f[N];bool vis[N];int dep[N],deep[N];int max_son[N];int maxn,root;void Add(int x,int y){ to[++cnt]=y,nex[cnt]=h[x],h[x]=cnt; return;}void dfs1(int x,int tot){ vis[x]=1; for(int i=h[x];i;i=nex[i]) if(!vis[to[i]]) dfs1(to[i],tot+1); if(tot>maxn) maxn=tot,root=x; return ;}int dfs2(int x,int tot,int last){ vis[x]=0;f[x]=last;dep[x]=tot; int sum=0; for(int i=h[x];i;i=nex[i]) if(vis[to[i]]) sum=max(sum,dfs2(to[i],tot+1,x)); sum=max(sum,tot); maxn=max(maxn,sum); max_son[x]=sum; return sum;}void work(int u,int v){ int t,len,ans=0; if(dep[u]>=dep[v]) t=u;else if(dep[v]>dep[u]) t=v; int minn=min(dep[v],dep[u]); len=minn+1; ans=minn+1; ans=max(ans,max_son[t]-(dep[t]-minn-1)); while(dep[t]>len) { ans=max(ans,max_son[t]-(dep[t]-len)); len++,t=f[t]; } return ;}int main(){ scanf("%d%d",&n,&m); for(int i=1,x,y;i