BZOJ——1602: [Usaco2008 Oct]牧场行走 || 洛谷—— P2912 [USACO08OCT]牧场散步Pasture Walking

http://www.lydsy.com/JudgeOnline/problem.php?id=1602

||

https://www.luogu.org/problem/show?pid=2912

题目描述

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)对奶牛之间的距离。

输入

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

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

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

输出

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

样例输入

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

样例输出

2
7

提示

来源

资格赛

练习模板

倍增：

 #include <algorithm>
 #include <cstdio>

 using namespace std;

 const int N(+);
 int n,q,x,y,z;
 int dad[N<<][],deep[N<<];
 int dis[N<<];
 int sumedge,head[N<<];
 struct Edge
 {
     int from,to,next,dis;
     Edge(int from=,int to=,int next=,int dis=) :
         from(from),to(to),next(next),dis(dis) {}
 }edge[N<<];

 int add(int from,int to,int dis)
 {
     edge[++sumedge]=Edge(from,to,head[from],dis);
     return head[from]=sumedge;
 }

 void DFS(int x)
 {
     deep[x]=deep[dad[x][]]+;
     for(int i=;dad[x][i];i++)
         dad[x][i+]=dad[dad[x][i]][i];
     for(int i=head[x];i;i=edge[i].next)
         if(!deep[edge[i].to])
         {
             dad[edge[i].to][]=x;
             dis[edge[i].to]=dis[x]+edge[i].dis;
             DFS(edge[i].to);
         }
 }

 int LCA(int x,int y)
 {
     if(deep[x]>deep[y]) swap(x,y);
     for(int i=;i>=;i--)
         if(deep[x]<=deep[dad[y][i]]) y=dad[y][i];
     if(x==y) return x;
     for(int i=;i>=;i--)
         if(dad[x][i]!=dad[y][i])
             x=dad[x][i],y=dad[y][i];
     return dad[x][];
 }

 int main()
 {
     scanf("%d%d",&n,&q);
     for(int i=;i<n;i++)
     {
         scanf("%d%d%d",&x,&y,&z);
         add(x,y,z); add(y,x,z);
     }
     DFS();
     for(;q;q--)
     {
         scanf("%d%d",&x,&y);
         printf("%d\n",dis[x]+dis[y]-(dis[LCA(x,y)]<<));
     }
     return ;
 }

然后是树剖的~

 #include <algorithm>
 #include <cstdio>
 #include <vector>

 using namespace std;

 const int N(+);
 vector< pair<int,int> >vec[N];
 int n,q,x,y,z,dis[N];
 int dad[N],deep[N],size[N],top[N];

 void DFS(int x)
 {
     size[x]=; deep[x]=deep[dad[x]]+;
     for(int i=;i<vec[x].size();i++)
         if(dad[x]!=vec[x][i].first)
         {
             dad[vec[x][i].first]=x;
             dis[vec[x][i].first]=dis[x]+vec[x][i].second;
             DFS(vec[x][i].first);
             size[x]+=size[vec[x][i].first];
         }
 }

 void DFS_(int x)
 {
     int t=; if(!top[x]) top[x]=x;
     for(int i=;i<vec[x].size();i++)
         if(dad[x]!=vec[x][i].first&&size[t]<size[vec[x][i].first]) t=vec[x][i].first;
     if(t) top[t]=top[x],DFS_(t);
     for(int i=;i<vec[x].size();i++)
         if(dad[x]!=vec[x][i].first&&t!=vec[x][i].first) DFS_(vec[x][i].first);
 }

 int LCA(int x,int y)
 {
     while(top[x]!=top[y])
     {
         if(deep[top[x]]<deep[top[y]]) swap(x,y);
         x=dad[top[x]];
     }
     if(deep[x]>deep[y]) swap(x,y);
     return x;
 }

 int main()
 {
     scanf("%d%d",&n,&q);
     for(int i=;i<n;i++)
     {
         scanf("%d%d%d",&x,&y,&z);
         vec[x].push_back(make_pair(y,z));
         vec[y].push_back(make_pair(x,z));
     }
     DFS(); DFS_();
     for(;q;q--)
     {
         scanf("%d%d",&x,&y);
         printf("%d\n",dis[x]+dis[y]-dis[LCA(x,y)]*);
     }
     return ;
 }