求LCA（最近公共祖先）

2019-11-11 05:32:39

字体：大中小

来源：转载

供稿：网友

算法1：树上倍增

//HDU 2586#include <cstdio>#include <algorithm>#include <cstring>#define maxn 40000+5#define INF 999999999using namespace std;int n,m,T,Q,head[maxn],x,y,z,vis[maxn],fa[maxn],cost[maxn],dep[maxn],maxcost[maxn][20],anc[maxn][20];struct xx{ int v,next,q;}b[maxn];void add(int u,int v,int q){ b[++m]=(xx){v,head[u],q}; head[u]=m;}int dfs(int t){ vis[t]=1; for (int k=head[t];k!=0;k=b[k].next) if (!vis[b[k].v]) fa[b[k].v]=t,cost[b[k].v]=b[k].q,dep[b[k].v]=dep[t]+1,dfs(b[k].v);}int ST(){ for (int i=1;i<=n;i++) { anc[i][0]=fa[i];maxcost[i][0]=cost[i]; for (int j=1;(1<<j)<=n;j++) anc[i][j]=0; } for (int j=1;(1<<j)<=n;j++) for (int i=1;i<=n;i++) { int a=anc[i][j-1]; anc[i][j]=anc[a][j-1]; maxcost[i][j]=maxcost[i][j-1]+maxcost[a][j-1]; }}int query(int p,int q){ int ans=0,log; if (dep[p]<dep[q])swap(p,q); for (log=1;(1<<log)<=dep[p];log++);log--; for (int i=log;i>=0;i--) if (dep[p]-(1<<i)>=dep[q]) ans+=maxcost[p][i],p=anc[p][i]; if (p==q) return ans; for (int i=log;i>=0;i--) if (anc[p][i]&&anc[p][i]!=anc[q][i]) { ans+=maxcost[p][i]+maxcost[q][i]; p=anc[p][i];q=anc[q][i] ; } ans+=maxcost[p][0]+maxcost[q][0]; return ans;}int main(){ scanf("%d",&T); while (T--) { m=0; memset(head,0,sizeof(head)); memset(fa,0,sizeof(fa)); memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&Q); for (int i=1;i<n;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); dfs(1); ST(); while (Q--) { scanf("%d%d",&x,&y); PRintf("%d/n",query(x,y)); } } return 0;}

算法2：Tarjan

include <cstdio>#include <algorithm>#include <cstring>#define maxn 80000+5using namespace std;int Q,dis[maxn],T,x,y,z,n,m,num,head[maxn],vis[maxn],fa[maxn],h[maxn],ans[maxn];struct xx{ int v,next,q;}b[maxn];struct yy{ int u,v,next,num;}b2[405];void add(int u,int v,int q){ b[++m]=(xx){v,head[u],q}; head[u]=m;}void _add(int u,int v,int q){ b2[++num]=(yy){u,v,h[u],q}; h[u]=num;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int dfs(int t,int val){ dis[t]=val; fa[t]=t; //vis[t]=1; for (int k=head[t];k!=0;k=b[k].next) { int v=b[k].v; if (!vis[v]) vis[v]=1,dfs(v,val+b[k].q),fa[v]=t; } for (int k=h[t];k!=0;k=b2[k].next) if (vis[b2[k].v]) { ans[b2[k].num]=dis[t]+dis[b2[k].v]-(dis[find(b2[k].v)]*2); } return 0;}int main(){ scanf("%d",&T); while (T--) { m=num=0; memset(head,0,sizeof(head)); memset(h,0,sizeof(h)); memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&Q); for (int i=1;i<n;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); for (int i=1;i<=Q;i++) { scanf("%d%d",&x,&y); _add(x,y,i); _add(y,x,i); } vis[1]=1;dfs(1,0); for (int i=1;i<=Q;i++) printf("%d/n",ans[i]); } return 0;}

被数据坑得很惨，开始先写了倍增，数组只开了40000，但是神奇的A了。So后来写Tarjan时也只开了40000，一直RE不明所以，找了很久错QAQ……然后把数组开了两倍大（双向边）就没有然后了……

上一篇：1013: [JSOI2008]球形空间产生器sphere

下一篇：Leetcode 139 - Word Break（线性dp）