?

【題目鏈接】?http://poj.org/problem?id=1986

?

【題目大意】

　　給出一棵樹(shù)，問(wèn)任意兩點(diǎn)間距離。

?

【題解】

　　u,v之間距離為dis[u]+dis[v]-2*dis[LCA(u,v)]

?

【代碼】

#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=300010; int d[N],num[N],dis[N],ed=0,x,y,c,n,m,i,w[N],v[N],vis[N],f[N],g[N],nxt[N],size[N],son[N],st[N],en[N],dfn,top[N],t;char ch; void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} void add_edge(int x,int y,int _w){v[++ed]=y;w[ed]=_w;nxt[ed]=g[x];g[x]=ed;} void dfs(int x){size[x]=1;for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){f[v[i]]=x,d[v[i]]=d[x]+1;dis[v[i]]=dis[x]+w[i];dfs(v[i]),size[x]+=size[v[i]];if(size[v[i]]>size[son[x]])son[x]=v[i];} } void dfs2(int x,int y){st[x]=++dfn;top[x]=y;if(son[x])dfs2(son[x],y);for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);en[x]=dfn; } int lca(int x,int y){for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;}return d[x]<d[y]?x:y; } void init(){ memset(g,dfn=ed=0,sizeof(g));memset(v,0,sizeof(v));memset(nxt,0,sizeof(nxt));memset(son,-1,sizeof(son)); } int main(){while(~scanf("%d%d",&n,&m)){init();while(m--){int u,v,w; char op[10];scanf("%d%d%d%s",&u,&v,&w,op);add_edge(u,v,w);add_edge(v,u,w);}dfs(1);dfs2(1,1);scanf("%d",&m);while(m--){int u,v;scanf("%d%d",&u,&v);printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/forever97/p/poj1986.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1986 Distance Queries（LCA）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。