我想我经大神点拨后终于明白了。。。回学校再写吧
时间限制：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<iostream> #include<cstdio> #include<queue> #include<vector> #include<algorithm> #include<cstring> 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<<ans<<endl; return ; } int main() { scanf("%d%d",&n,&m); for(int i=1,x,y;i<n;i++) { scanf("%d%d",&x,&y); Add(x,y);Add(y,x); } f[1]=0; dfs1(1,0); maxn=0; dfs2(root,0,0); for(int i=1,u,v;i<=m;i++) { scanf("%d%d",&u,&v); work(u,v); } return 0; }
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<algorithm> #include<cstring> 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 ",maxn); return; }else { int ans; ans=maxn-(dep[t]-minn)+1; ans=max(ans,minn+1+(dep[t]-minn)/2); printf("%d ",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 ",ans); return ; } int main() { scanf("%d%d",&n,&m); for(int i=1,x,y;i<n;i++) { scanf("%d%d",&x,&y); Add(x,y);Add(y,x); } f[1]=0; dfs1(1,0); maxn=0; dfs2(root,0,0); for(int i=1,u,v;i<=m;i++) { scanf("%d%d",&u,&v); work(u,v); } return 0; }
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<algorithm> #include<cstring> 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<n;i++) { scanf("%d%d",&x,&y); Add(x,y);Add(y,x); } f[1]=0; dfs1(1,0); maxn=0; dfs2(root,0,0); for(int i=1,u,v;i<=m;i++) { scanf("%d%d",&u,&v); work(u,v); } return 0; }