poj 2763LCA

#include<cstdio> #include<cstring> #include<algorithm> #define MAX_N 100010 using namespace std; struct point { int to,next,id; }G[MAX_N]; int head[MAX_N],depth[MAX_N],bit[MAX_N],in[MAX_N],out[MAX_N],parent[21][MAX_N],vs[MAX_N],val[MAX_N]; int cnt,k; void add_edge(int from,int to,int id) { G[cnt].to=to; G[cnt].id=id; G[cnt].next=head[from]; head[from]=cnt++; } void dfs(int v,int p,int d) { depth[v]=d; parent[0][v]=p; for(int i=1;i<20;i++) { if(parent[i][v]==-1) parent[i][v]=-1; else parent[i][v]=parent[i-1][parent[i-1][v]]; } for(int i=head[v];i!=-1;i=G[i].next) { point &e=G[i]; if(e.to==p) continue; in[e.id]=vs[e.to]=++k; dfs(e.to,v,d+1); out[e.id]=++k; } } int LCA(int u,int v) { if(depth[u]>depth[v]) swap(u,v); for(int k=0;k<20;k++) { if((depth[v]-depth[u])>>k&1) v=parent[k][v]; } if(u==v) return u; for(int k=19;k>=0;k--) { if(parent[k][u]!=parent[k][v]) { u=parent[k][u]; v=parent[k][v]; } } return parent[0][v]; } int sum(int i) { int res=0; while(i>0) { res+=bit[i]; i-=i&-i; } return res; } void add(int i,int v) { while(i<=k) { bit[i]+=v; i+=i&-i; } } int main() { memset(head,-1,sizeof(head)); cnt=k=0; int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b,c; char str[100]; scanf("%d%d%d%s",&a,&b,&c,str); add_edge(a,b,i); add_edge(b,a,i); val[i]=c; } dfs(1,-1,0); memset(bit,0,sizeof(bit)); for(int i=1;i<=m;i++) { add(in[i],val[i]); add(out[i],-val[i]); } int Q; scanf("%d",&Q); while(Q--) { int a,b; scanf("%d%d",&a,&b); printf("%d\n",sum(vs[a])+sum(vs[b])-2*sum(vs[LCA(a,b)])); } }