POJ 1986 LCA模板加强点的
题意算是见过的最龌龊的了，你妹的，都不知道一共有多少个顶点，RE几次后立马把数组开到10W级别的；
#include<cstdio>#include<string.h>#include<algorithm>#include<vector>#include<stdlib.h>#include<cmath>#include<queue>#include<set>#include<map>#include<list>using namespace std;const int N=100015; struct node { int u,next,w; }edge[N*2],Q[N]; int father[N],dist[N],ance[N],head[N],st,et,qhead[N],res[N]; bool flag[N],vis[N]; int find(int x) { return x==father[x]?x:father[x]=find(father[x]); } void add(int u,int v,int val) { edge[st].u=v; edge[st].next=head[u]; edge[st].w=val; head[u]=st++; } void Qadd(int u,int v,int i) { Q[et].u=v; Q[et].next=qhead[u]; Q[et].w=i; qhead[u]=et++; } void dfs(int u,int val) { dist[u]=val; ance[u]=u; vis[u]=true; for(int i=head[u];i!=-1;i=edge[i].next) { if(!vis[edge[i].u]) { dfs(edge[i].u,edge[i].w+val); father[find(edge[i].u)]=find(u); ance[find(u)]=u; } } flag[u]=true; for(int i=qhead[u];i!=-1;i=Q[i].next) { if(flag[Q[i].u]) { res[Q[i].w]=dist[u]+dist[Q[i].u]-2*dist[ance[find(Q[i].u)]]; } } } void init() { st=0; et=0; memset(head,-1,sizeof(head)); memset(qhead,-1,sizeof(qhead)); memset(flag,false,sizeof(flag)); memset(ance,0,sizeof(ance)); memset(dist,0,sizeof(dist)); memset(res,0,sizeof(res)); memset(vis,false,sizeof(vis)); } int main() {int n,k;while(~scanf("%d%d",&n,&k)){init(); for(int i=0;i<=n;i++) { father[i]=i; } int u,v,val; char op[3]; while(k--) { scanf("%d %d %d %s",&u,&v,&val,op); add(u,v,val); add(v,u,val); } int t; scanf("%d",&t); for(int i=0;i<t;i++) { scanf("%d%d",&u,&v); Qadd(u,v,i); Qadd(v,u,i); } dfs(1,0); for(int i=0;i<t;i++) { printf("%d\n",res[i]); }} return 0; }