| ||||||||||
| 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 | |||||||||
小草版tarjan 282msIn Reply To:我的TARJAN 要1.2+ 好慢,谁有好的模板? Posted by:longpo at 2009-04-25 03:12:39 //tarjan 282ms
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node{
int u,v,bh,dis;
}a[40010];
int du[40010],p[40010],top,bhtop,now;
int f(int x)
{
if(x!=p[x])p[x]=f(p[x]);
return p[x];
}
struct treenode{
int to,dis;
treenode*next;
}*list[40010],edge[80010];
struct checknode{
int source,target,ns,nt,ans,ybh;
}check[10010];
int newbh[40010],nowdis,dis[40010];
bool op1(checknode x,checknode y){return x.nt<y.nt;}
bool op2(checknode x,checknode y){return x.ybh<y.ybh;}
void doit(int k,int from) {
for (treenode*p=list[k];p;p=p->next) if (p->to!=from) {
nowdis+=p->dis;
doit(p->to,k);
nowdis-=p->dis;
}
dis[k]=nowdis;
newbh[k]=++bhtop;
}
int m;
void doit2(int k,int from) {
for (treenode*poi=list[k];poi;poi=poi->next) if (poi->to!=from) {
doit2(poi->to,k);
p[poi->to]=f(k);
// printf("%d %d \n",poi->to,k);
}
while (now<=m&&check[now].nt==newbh[k]) {
int fa=f(check[now].source);
check[now].ans=dis[check[now].source]+dis[check[now].target]-dis[fa]-dis[fa];
now++;
}
}
int main()
{
int n;
// freopen("c:\\input.txt","r",stdin);
scanf("%d%*d",&n);
for (int i=1;i<n;i++) {
scanf("%d%d%d%*c%*c",&a[i].u,&a[i].v,&a[i].dis);
du[a[i].v]++;
du[a[i].u]++;
edge[++top].to=a[i].v;
edge[top].next=list[a[i].u];
edge[top].dis=a[i].dis;
list[a[i].u]=edge+top;
edge[++top].to=a[i].u;
edge[top].next=list[a[i].v];
edge[top].dis=a[i].dis;
list[a[i].v]=edge+top;
}
scanf("%d",&m);
for (int i=1;i<=m;i++) scanf("%d%d",&check[i].source,&check[i].target);
int root;
for (int i=1;i<=n;i++) if (du[i]==1) {root=i;break;}
for (int i=1;i<=n;i++) p[i]=i;
doit(root,0);
for (int i=1;i<=m;i++) {
check[i].ns=newbh[check[i].source];
check[i].nt=newbh[check[i].target];
if (check[i].ns>check[i].nt) {
swap(check[i].ns,check[i].nt);
swap(check[i].source,check[i].target);
}
check[i].ybh=i;
}
sort(check+1,check+m+1,op1);
now=1;
doit2(root,0);
sort(check+1,check+m+1,op2);
for (int i=1;i<=m;i++) printf("%d\n",check[i].ans);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator