网站视差怎么做/广告投放运营主要做什么

题意

一个游客到一个国家旅行，这个国家原来有n个城市,n-1条路，游客规划了q条旅行路线。现在这个国家要新修一条路，问新修这条路后q条旅行路线分别可以节约多少时间。

题解

LCA模板题。模板可以参考:http://blog.csdn.net/y990041769/article/details/40887469

注意事项

注意数组开大些，否则可能会出现RE或RF错误。

代码

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 100010
#define INF 1e9using namespace std;
struct{int v,cost,next;
}edge[MAXN*2];
int head[MAXN*2];
int deep[MAXN*2],used[MAXN*2],vis[MAXN*2],first[MAXN*2],len[MAXN*2];
int tot,df;
int dp[MAXN*2][20];void addEdge(int u,int v,int c){edge[tot].v=v;edge[tot].cost=c;edge[tot].next=head[u];head[u]=tot++;
}void dfs(int u,int dep){used[u]=1,first[u]=df,deep[df]=dep,vis[df++]=u;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(!used[v]){len[v]=len[u]+edge[i].cost;dfs(v,dep+1);deep[df]=dep;vis[df++]=u;}}
}void newst(int n){for(int i=1;i<=n;i++){dp[i][0]=i;}for(int j=1;(1<<j)<=n;j++){for(int i=1;i+(1<<j)-1<=n;i++){int x=dp[i][j-1];int y=dp[i+(1<<(j-1))][j-1];dp[i][j]=deep[x]>deep[y]?y:x;}}
}int rmq(int l,int r){int k=0;while(1<<(k+1)<=(r-l+1)){k++;}int x=dp[l][k];int y=dp[r-(1<<k)+1][k];return deep[x]>deep[y]?y:x;
}int lca(int u,int v){int x=first[u],y=first[v];if(x>y){int c=x;x=y;y=c;}return vis[rmq(x,y)];
}int main()
{int kase;scanf("%d",&kase);for(int ks=1;ks<=kase;ks++){printf("Case #%d:\n",ks);int n,q;scanf("%d%d",&n,&q);df=1,tot=1;memset(head,-1,sizeof(head));memset(used,0,sizeof(used));memset(deep,INF,sizeof(deep));for(int i=0;i<n-1;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);addEdge(a,b,c);addEdge(b,a,c);}dfs(1,0);newst(2*n-1);int newx,newy,newz;scanf("%d%d%d",&newx,&newy,&newz);while(q--){int a,b;scanf("%d%d",&a,&b);int anx=len[a]+len[newx]-2*len[lca(a,newx)];int any=len[a]+len[newy]-2*len[lca(a,newy)];int bnx=len[b]+len[newx]-2*len[lca(b,newx)];int bny=len[b]+len[newy]-2*len[lca(b,newy)];int anb=len[a]+len[b]-2*len[lca(a,b)];int ans=min(anb,anx+bny+newz);ans=min(ans,any+bnx+newz);//printf("%d  %d  %d ",b,newx,lca(b,newx));printf("%d\n",anb-ans);}}return 0;
}