1 条题解
-
1
简化题意:有一棵 个点的树, 组询问,每次询问回答两点间的距离。
令 表示 到 的距离,根节点为 ,则有 $dis[i][j]=dis[rt][i]+dis[rt][j]-2×dis[rt][lca(i,j)]$ ,按照题意打即可。
#include<bits/stdc++.h> using namespace std; #define ll long long #define sort stable_sort #define endl '\n' struct node { int nxt,to,w; }e[100001]; int head[100001],dep[100001],dis[100001],fa[100001][25],N,cnt=0; void add(int u,int v,int w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void dfs(int x,int father,int w) { fa[x][0]=father; dep[x]=dep[father]+1; dis[x]=dis[father]+w; for(int i=1;(1<<i)<=dep[x];i++) { fa[x][i]=fa[fa[x][i-1]][i-1]; } for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=father) { dfs(e[i].to,x,e[i].w); } } } int lca(int x,int y) { if(dep[x]>dep[y]) { swap(x,y); } for(int i=N;i>=0;i--) { if(dep[x]+(1<<i)<=dep[y]) { y=fa[y][i]; } } if(x==y) { return x; } else { for(int i=N;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } } int main() { int n,m,k,i,u,v,w,l,r; char pd; cin>>n>>m; for(i=1;i<=m;i++) { cin>>u>>v>>w>>pd; add(u,v,w); add(v,u,w); } N=log2(n)+1; dfs(1,0,1); cin>>k; for(i=1;i<=k;i++) { cin>>l>>r; cout<<dis[l]+dis[r]-2*dis[lca(l,r)]<<endl; } return 0; }
- 1
信息
- ID
- 3364
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 10
- 已通过
- 4
- 上传者