MABODX
Accept:17
Submit:88
Time Limit:4000MS
Memory Limit:65536KB
Description
There is a country which has N city. Because The king spend littlemoney on the road ,so there is one and only one path from any cityto another city,every city has a apple tree.The apple in one citywhich has only one apple tree is the same.
Now The king wants to ask Bobo some questions .The king wants toknow if he walk from A city to B city and pick apples from the appletree when he pass one city (including A city and B city) what is thesum value of apples.But Bobo can't the question so he turns to yourhelp.
Input
There are many cases.
The first line of every case is N andM.N(1<=N<=50000) means N city, M(1<=M<=50000) means Mquestion .
Then N-1 line represent the roadbetween the country. Then the N line has N number the ith number onthe N line means the value of the apple in the ith city(the value isless than 10000) .
Then M line .Each line has 2 numberA(1<=A<=N) and B(1<=B<=N) ,means king ask if he walk fromcity A to city B.
Output
The sum value of appple of everyquestion. Output one line one answer.
Sample Input
3 2
1 2
1 3
5 7 10
1 3
3 2
Sample Output
15
22
Source
mabodx
此题用LCA做，首先预处理dfs求出每一点到根节点的权值，再LCA即可
#include<cstdio>
#include<string.h>
using namespace std;
int n,m,num[50100],sum[50100],ans[50100];
int head1[50100],head2[50100],cnt,f[50100],ff[50100];
bool flag[50100];
struct Edge{
int f,v,id,next;
}edge[50100*7];
void addedge(int u,int v,int id,int *head){
edge[cnt].f=u;
edge[cnt].v=v;
edge[cnt].id=id;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].f=v;
edge[cnt].v=u;
edge[cnt].id=id;
edge[cnt].next=head[v];
head[v]=cnt++;
}
void dfs(int u,int father){
int i;
for(i=head1[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v!=father){
sum[v]=sum[u]+num[v];
dfs(v,u);
}
}
}
int find(int u){
int s;
for(s=u;f[s]!=s;s=f[s]);
while(s!=u){
int tmp=f[u];
f[u]=s;
u=tmp;
}
return s;
}
void tarjan(int u,int father){
int i;
f[u]=u;
for(i=head1[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v!=father){
tarjan(v,u);
f[v]=u;
}
}
flag[u]=1;
for(i=head2[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(flag[v]){
int t=find(v);
ans[edge[i].id]=sum[edge[i].f]+sum[edge[i].v]-2*sum[t]+num[t];
}
}
}
int main(){
int i,j;
while(scanf("%d %d",&n,&m)==2){
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
memset(flag,0,sizeof(flag));
memset(ff,0,sizeof(ff));
memset(sum,0,sizeof(sum));
memset(f,0,sizeof(f));
cnt=0;
for(i=1;i<n;i++){
int u,v;
scanf("%d %d",&u,&v);
addedge(u,v,0,head1);
}
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
for(i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
addedge(u,v,i,head2);
}
sum[1]=num[1];
dfs(1,0);
tarjan(1,0);
for(i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
}
打比赛时我一直用的带权值的并查集做，一直WA，现在也没查出错，望路过的大牛能够指正
#include<cstdio>
#include<string.h>
using namespace std;
int n,m,num[50100],sum[50100],ans[50100];
int head1[50100],head2[50100],head3[50100],cnt,f[50100],ff[50100];
bool vis[50100],flag[50100];
struct Edge{
int f,v,id,next;
}edge[50100*7];
void addedge(int u,int v,int id,int *head){
edge[cnt].f=u;
edge[cnt].v=v;
edge[cnt].id=id;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].f=v;
edge[cnt].v=u;
edge[cnt].id=id;
edge[cnt].next=head[v];
head[v]=cnt++;
}
int find(int u){
if(f[u]==u){
sum[u]=num[u];
return u;
}
f[u]=find(f[u]);
sum[u]=sum[ff[u]]+num[u];
return f[u];
}
void tarjan(int u){
int i;
f[u]=u;
for(i=head1[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(!vis[v] ){
vis[v]=1;
tarjan(v);
f[v]=u;
ff[v]=u;
find(v);
}
}
flag[u]=1;
for(i=head2[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(flag[v]){
int t=find(v);
edge[cnt].v=i;
edge[cnt].next=head3[t];
head3[t]=cnt++;
}
}
for(i=head3[u];i!=-1;i=edge[i].next){
int j=edge[i].v;
int uu=edge[j].f;
int vv=edge[j].v;
int id=edge[j].id;
find(uu);
ans[id]=sum[uu]+sum[vv]-num[u];
}
}
int main(){
int i,j;
while(scanf("%d %d",&n,&m)==2){
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
memset(head3,-1,sizeof(head3));
memset(vis,0,sizeof(vis));
memset(flag,0,sizeof(flag));
memset(ff,0,sizeof(ff));
memset(sum,0,sizeof(sum));
memset(f,0,sizeof(f));
cnt=0;
for(i=1;i<n;i++){
int u,v;
scanf("%d %d",&u,&v);
addedge(u,v,0,head1);
}
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
for(i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
addedge(u,v,i,head2);
}
vis[1]=1;
tarjan(1);
for(i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
}