HDU-2586-裸LCA入门-tarjan离线

http://acm.hdu.edu.cn/showproblem.php?pid=2586

给出一颗树和边权，询问两点距离。

考虑tarjan离线做法，做法很巧妙，当前进行到u，对他的儿子v，当v子树tarjan完成之后把v合并到u上。当遍历完所有v之后，对与u有关的询问进行查找，若第二个询问点v被访问过，那么lca(u,v)就是v目前被合并到的根上。还有记录d[u]表示根到u的距离。

　　最后答案就是d[u]+d[v]-2*d[lca(u,v)]。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<map>

 #include<set>

 #include<stack>

 #include<deque>

 #include<bitset>

 #include<unordered_map>

 #include<unordered_set>

 #include<queue>

 #include<cstdlib>

 #include<ctype.h>

 #include<ctime>

 #include<functional>

 #include<algorithm>

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define pii pair<int,int>

 #define mp make_pair

 #define pb push_back

 #define fi first

 #define se second

 #define inf 0x3f3f3f3f

 #define debug puts("debug")

 #define mid ((L+R)>>1)

 #define lc (id<<1)

 #define rc (id<<1|1)

 const int maxn=;

 const int maxm=;

 const double PI=acos(-1.0);

 const double eps=1e-;

 const LL mod=1e9+;

 LL gcd(LL a,LL b){return b==?a:gcd(b,a%b);}

 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}

 LL qpow(LL a,LL b,LL c){LL r=; for(;b;b>>=,a=a*a%c)if(b&)r=r*a%c;return r;}

 template<class T>

 void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}

 struct Edge{int u,v,w,next;};

 vector<pii>g[maxn],q[maxn];

 int d[maxn],f[maxn],qu[],qv[],ans[];

 bool vis[maxn];

 int getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}

 void tarjan(int u){

     vis[u]=;

     for(pii e:g[u]){

         int v=e.fi,w=e.se;

         if(!vis[v]){

             d[v]=d[u]+w;

             tarjan(v);

             f[v]=u;

         }

     }

     for(pii e:q[u]){

         int v=e.fi,id=e.se;

         if(vis[v]){

             ans[id]=getf(v);

         }

     }

 }

 int main(){

     int t,n,m,i,j,u,v,w;

     scanf("%d",&t);

     while(t--){

         scanf("%d%d",&n,&m);

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

             g[i].clear();

             q[i].clear();

             f[i]=i;

             vis[i]=;

         }

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

             scanf("%d%d%d",&u,&v,&w);

             g[u].pb(mp(v,w));

             g[v].pb(mp(u,w));

         }

         for(i=;i<=m;++i){

             scanf("%d%d",qu+i,qv+i);

             q[qu[i]].pb(mp(qv[i],i));

             q[qv[i]].pb(mp(qu[i],i));

         }

         tarjan();

         for(i=;i<=m;++i){

             printf("%d\n",d[qu[i]]+d[qv[i]]-*d[ans[i]]);

         }

     }

     return ;

 }

接着用ST在线做法又做了一遍。如果题目强制在线的话，tarjan做法就gg了，我们提前不知道询问便无法离线做了。

ST做法是每次访问到一个节点就记录下当前的节点值和深度，当查询lca(u,v)的时候，先找到u和v第一次访问到的位置L和R（L<=R)，

然后在[L,R]中找到一个深度最小的点，他对应的节点值w=lca(u,v)。RMQ问题，使用ST处理O(nlog(n))。询问就可以O(1)啦。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<map>

 #include<set>

 #include<stack>

 #include<deque>

 #include<bitset>

 #include<unordered_map>

 #include<unordered_set>

 #include<queue>

 #include<cstdlib>

 #include<ctype.h>

 #include<ctime>

 #include<functional>

 #include<algorithm>

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define pii pair<int,int>

 #define mp make_pair

 #define pb push_back

 #define fi first

 #define se second

 #define inf 0x3f3f3f3f

 #define debug puts("debug")

 #define mid ((L+R)>>1)

 #define lc (id<<1)

 #define rc (id<<1|1)

 const int maxn=;

 const int maxm=;

 const double PI=acos(-1.0);

 const double eps=1e-;

 const LL mod=1e9+;

 LL gcd(LL a,LL b){return b==?a:gcd(b,a%b);}

 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}

 LL qpow(LL a,LL b,LL c){LL r=; for(;b;b>>=,a=a*a%c)if(b&)r=r*a%c;return r;}

 template<class T>

 void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}

 struct Edge{int u,v,w,next;};

 vector<pii>g[maxn];

 vector<int>dep,idx;

 int f[maxn*][],d[maxn],p[maxn];

 void dfs(int u,int o,int fa){

     p[u]=idx.size();

     idx.pb(u),dep.pb(o);

     for(pii e:g[u]){

         int v=e.fi,w=e.se;

         if(v!=fa){

             d[v]=d[u]+w;

             dfs(v,o+,u);

             idx.pb(u),dep.pb(o);

         }

     }

 }

 void ST(int n){

     for(int i=;i<n;++i)f[i][]=i;

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

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

             f[i][j]=dep[f[i][j-]]<dep[f[i+(<<(j-))][j-]]?f[i][j-]:f[i+(<<(j-))][j-];

         }

     }

 }

 int ask(int L,int R){

     int k=;

     while((<<(+k))<=R-L+)k++;

     return dep[f[L][k]]<dep[f[R-(<<k)+][k]]?idx[f[L][k]]:idx[f[R-(<<k)+][k]];

 }

 int main(){

     int t,n,m,i,j,u,v,w;

     scanf("%d",&t);

     while(t--){

         idx.clear();

         dep.clear();

         scanf("%d%d",&n,&m);

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

             g[i].clear();

         }

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

             scanf("%d%d%d",&u,&v,&w);

             g[u].pb(mp(v,w));

             g[v].pb(mp(u,w));

         }

         dfs(,,);

         ST(idx.size());

     //    prt(idx);

     //    prt(dep);

         while(m--){

             scanf("%d%d",&u,&v);

             int L=p[u],R=p[v];

             if(L>R)swap(L,R);

             printf("%d\n",d[u]+d[v]-*d[ask(L,R)]);

         }

     }

     return ;

 }

 /*

 5

 7 7

 1 2 1

 1 3 1

 2 4 1

 2 5 1

 5 6 1

 5 7 1

 */

　　综上两种方法而言，我感觉思想都是类似是，就是u-->v这条路一定经过他们的共同祖先，这中间过程中经过若干个点，我们要想办法找到深度最小的那个点，显然他只会被经过一次，就是LCA。

巴特西

HDU-2586-裸LCA入门-tarjan离线

最新文章

热门文章