bzoj 1602 [Usaco2008 Oct]牧场行走（LCA模板）

时间：2023-03-09 07:10:16
bzoj 1602 [Usaco2008 Oct]牧场行走（LCA模板）

1602: [Usaco2008 Oct]牧场行走

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 379  Solved: 216
[Submit][Status][Discuss]

Description

N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。

这n块土地被n-1条边连接。

奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。

这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。

这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。

Input

*第一行：两个被空格隔开的整数：N和Q

*第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI

*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。

Output

*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。

Sample Input

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Sample Output

2
7

HINT

Source

【代码】

//O(qlogn)

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<vector>

 #include<iostream>

 #define FOR(a,b,c) for(int a=(b);a<(c);a++)

 using namespace std;

 const int maxn = +;

 const int maxd = ;

 struct Edge{ int u,v,w;

 };

 vector<int> G[maxn];

 vector<Edge> es;

 int d[maxn],dist[maxn];

 int p[maxn][maxd],pd[maxn][maxd];

 void addedge(int u,int v,int w) {

     es.push_back((Edge){u,v,w});

     int m=es.size(); G[u].push_back(m-);

 }

 void dfs(int u,int fa) {    //构造dist

     for(int i=;i<G[u].size();i++) {

         Edge e=es[G[u][i]];

         int v=e.v;

         if(v!=fa) {

             d[v]=d[u]+; dist[v]=dist[u]+e.w;

             p[v][]=u , pd[v][]=e.w;

             dfs(v,u);

         }

     }

 }

 int query(int u,int v) {    //查询

     if(d[v]>d[u]) swap(u,v);

     for(int i=maxd-;i>=;i--)

         if(d[p[u][i]]>=d[v])  u=p[u][i];    //调整至同意高度

     if(u==v) return u;        //同一子树则返回

     for(int i=maxd-;i>=;i--)

          if(p[u][i]!=p[v][i])

              u=p[u][i] , v=p[v][i];        //查找lca

     return p[u][];

 }

 int n,q;

 void read(int& x) {

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     x=;

     while(isdigit(c))

         x=x*+c-'' , c=getchar();

 }

 int main() {

     read(n),read(q);

     int u,v,w;

     for(int i=;i<n;i++) {

         read(u),read(v),read(w);

         addedge(u,v,w) , addedge(v,u,w);

     }

     dfs(,-);

     for(int k=;k<maxd;k++) for(int i=;i<=n;i++) {        //构造倍增数组

         p[i][k]=p[p[i][k-]][k-];

         pd[i][k]=pd[i][k-]+pd[p[i][k-]][k-];

     }

     while(q--) {

         read(u),read(v);

         printf("%d\n",dist[u]+dist[v]-*dist[query(u,v)]);

     }

     return ;

 }

beizeng

//O(n+q)

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<vector>

 #include<iostream>

 using namespace std;

 const int maxn = +;

 const int maxq = +;

 struct Edge{ int u,v,w;

 };

 struct node { int v,i; };

 vector<int> G[maxn];

 vector<Edge> es;

 vector<node> que[maxn];

 int U[maxq],V[maxq];

 void addedge(int u,int v,int w) {

     es.push_back((Edge){u,v,w});

     int m=es.size(); G[u].push_back(m-);

 }

 int p[maxn];

 int find(int u) { return u==p[u]? u:p[u]=find(p[u]);

 }

 int dist[maxn];

 void dfs(int u,int fa) {    //求dist

     for(int i=;i<G[u].size();i++) {

         Edge e=es[G[u][i]];  int v=e.v;

         if(v!=fa)  dist[v]=dist[u]+e.w , dfs(v,u);

     }

 }

 int vis[maxn],lca[maxq];

 void tarjan(int u,int fa) {

     p[u]=u;

     for(int i=;i<G[u].size();i++) {

         Edge e=es[G[u][i]]; int v=e.v;

         if(v!=fa) tarjan(v,u),p[v]=u;    //递归处理 合并集合

     }

     vis[u]=;

     for(int i=;i<que[u].size();i++) {        //求与u相关的询问

         int v=que[u][i].v;

         if(vis[v]) lca[que[u][i].i]=find(v);

         //如果已经被访问 lca为v集合的代表元x //若v是u子则x=u 若非子则因u还未访问完集合并未向上合并所以代表元为lca

     }

 }

 int n,q;

 void read(int& x) {

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     x=;

     while(isdigit(c))

         x=x*+c-'' , c=getchar();

 }

 int main() {

     read(n),read(q);

     int u,v,w;

     for(int i=;i<n;i++) {

         read(u),read(v),read(w);

         addedge(u,v,w) , addedge(v,u,w);

     }

     for(int i=;i<q;i++) {

         read(u),read(v);

         U[i]=u , V[i]=v;

         que[u].push_back((node){v,i});

         que[v].push_back((node){u,i});

     }

     tarjan(n>>,-) , dfs(n>>,-);

     for(int i=;i<q;i++) {

         u=U[i] , v=V[i];

         int lc=lca[i];

         printf("%d\n",dist[u]+dist[v]-(dist[lc]<<));

     }

     return ;

 }

tarjan

LCA的一种比较快的写法

////////////////////////////////////////////////////

int siz[N],top[N],son[N],fa[N];

void dfs1(int u) {

	siz[u]=1,son[0]=0; dfn[u]=++dfsc;

	for(int i=0;i<g[u].size();i++) {

		int v=g[u][i];

		if(v!=fa[u]) {

			fa[v]=u; d[v]=d[u]+1;

			dfs1(v);

			siz[u]+=siz[v];

			if(siz[v]>siz[son[u]]) son[u]=v;

		}

	}

}

void dfs2(int u,int tp) {

	top[u]=tp;

	if(son[u]) dfs2(son[u],tp);

	for(int i=0;i<g[u].size();i++) {

		int v=g[u][i];

		if(v!=son[u] && v!=fa[u]) dfs2(v,v);

	}

}

int LCA(int u,int v) {

	while(top[u]!=top[v])

		if(d[top[u]]>=d[top[v]]) u=fa[top[u]];

		else v=fa[top[v]];

	return d[u]<d[v]? u:v;

}

////////////////////////////////////////////////

　　题目部分戳这：http://www.cnblogs.com/lidaxin/p/5115660.html

相关文章