| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴一个树链剖分的代码...由于没修改,所以就不用线段树啦,直接记个前缀和就好啦.... #include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define RG register int #define rep(i,a,b) for(RG i=a;i<=b;++i) #define per(i,a,b) for(RG i=a;i>=b;--i) #define ll long long #define inf (1<<29) #define maxn 100005 #define add(x,y,z) e[++cnt]=(E){y,head[x],z},head[x]=cnt using namespace std; int n,m,cnt,id,T; int head[maxn],val[maxn],sz[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn],dfn[maxn],node[maxn],imos[maxn]; struct E{ int v,next,val; }e[maxn<<1]; inline int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void dfs1(int u,int pa) { sz[u]=1,fa[u]=pa,dep[u]=dep[pa]+1; for(RG i=head[u];i;i=e[i].next) { int v=e[i].v; if(v==pa) continue; val[v]=e[i].val; dfs1(v,u); sz[u]+=sz[v]; if(sz[v]>sz[son[u]]) son[u]=v; } } void dfs2(int u,int tp) { dfn[u]=++id,top[u]=tp,node[id]=u; if(!son[u]) return; dfs2(son[u],tp); for(RG i=head[u];i;i=e[i].next) { if(e[i].v!=fa[u]&&e[i].v!=son[u]) dfs2(e[i].v,e[i].v); } } void lca() { int x=read(),y=read(),ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=imos[dfn[x]]-imos[dfn[top[x]]-1]; x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans+=imos[dfn[y]]-imos[dfn[x]]; printf("%d\n",ans); } int main() { n=read(),m=read(); rep(i,1,m) { RG a=read(),b=read(),c=read();getchar(); add(a,b,c),add(b,a,c); } dfs1(1,0); dfs2(1,0); rep(i,1,n) imos[i]=val[node[i]]+imos[i-1]; T=read(); rep(t,1,T) lca(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator