HDU2586(LCA)解题报告 Apare_xzc

HDU2586(LCA)解题报告

2019/3/18 xzc

题目链接：
How far away ？

2019/3/27又写了一次(1A)

• 这道题我寒假打牛客的时候学了一下LCA的倍增算法，当时找了HDU上的这道题，AC了。31ms,用得是最朴素的倍增，两个人先到同一个高度，然后两个人一起一步一往上移动直到相遇

/* HDU 2586 LCA(最朴素的倍增，一步一步往上挑，数据太水) Author:xzc 2019-01-28 23:54:52 Accepted 2586 31MS 4396K 1282 B G++ apareHDU */
#include <bits/stdc++.h> 
using namespace std;
const int maxn = 4e4+20;
struct Graph{
    int head[maxn],deep[maxn],fa[maxn],dis[maxn],tot,n;
    struct Edge{
        int to,next;
        long long d;
    }edge[maxn<<1];
    void init(int nn)
    {
        n = nn;
        tot = 0;
        memset(head,0,sizeof(head));
        memset(deep,0,sizeof(deep));
        deep[1] = 1; fa[1] = 0;dis[1] = 0; 
    }
    void addedge(int u,int v,long long dd)
    {
        edge[++tot].to = v;
        edge[tot].d = dd;
        edge[tot].next = head[u];
        head[u] = tot;
    }
    void dfs(int u)
    { 
        for(int i=head[u];i;i=edge[i].next)
        {
            int to = edge[i].to;
            if(deep[to]) continue;
            dis[to] = edge[i].d;
            fa[to] = u;
            deep[to] = deep[u]+1;
            dfs(to);
        }
    }
    void solve(int a,int b)
    {
        long long ans = 0;
        if(deep[a]>deep[b]) swap(a,b);
        while(deep[b]>deep[a]) ans+=dis[b],b=fa[b];
        while(b!=a) ans+=dis[a]+dis[b],b=fa[b],a=fa[a];
        printf("%lld\n",ans);
    }
}G; 
int main()
{
    long long dd;
    int T,n,m,u,v;cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        G.init(n);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%lld",&u,&v,&dd);
            G.addedge(u,v,dd);
            G.addedge(v,u,dd);
        }
        G.dfs(1); 
        while(m--)
        {
            scanf("%d%d",&u,&v);
            G.solve(u,v); 
        }
    }
   
    return 0;
}

• 最近学了主席树求静态区间第K大，老会长推荐去写那个书上第K大，于是我就先来学LCA了
  这次学的是nlogn预处理，O(1)查询的(dfs+RMQ)的算法

学习的时候是参考的这篇博客
这个是番茄学长给我推荐的topcoder上的我还没看完就去马鞍山吃烧烤了~
这个也是番茄学长给我推荐的中文写的

/* HDU2586 LCA(dfs+RMQ) Author: xzc 2019-03-18 10:36:20 Accepted 2586(HDU) 93MS 15832K 2730 B G++ apareHDU */
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
using namespace std;
const int maxn = 1e5+20;
struct Edge{
    int to,Next;
    LL d;
}edge[maxn];
int head[maxn],tot;
void initG()
{
   Mst(head,-1);
    tot = 0;
}
void addedge(int from,int to,LL d)
{
    edge[tot].to = to;
    edge[tot].d = d;
    edge[tot].Next = head[from];
    head[from] = tot++;
}

bool vis[maxn];
int First[maxn];///First[i]表示节点i在欧拉序中首次出现的位置
int deep[maxn*2],cnt;
int sequence[maxn*2]; ///存欧拉序中节点的编号
void initDFS()
{
    Mst(vis,0);
    cnt = 0;
}
//int fa[maxn];
LL dis[maxn]; ///记录该节点到根节点的距离
void dfs(int root,int dep) ///Mst(vis),cnt=0; fa[1] = 1;dis[1] = 0;
{
    vis[root] = true;
    sequence[++cnt] = root;
    deep[cnt] = dep;
    First[root] = cnt;
    for(int i=head[root];i!=-1;i=edge[i].Next)
    {
        int to = edge[i].to;
        if(vis[to]) continue;
        //fa[to] = root;
        dis[to] = dis[root] + edge[i].d;
        dfs(to,dep+1);
        sequence[++cnt] = root;
        deep[cnt] = dep;
    }
}
int Min[maxn*2][20]; ///log2(1e6)==19.9 log2(1e5) = 16.6 log2(8e4) =16.28
int Log2[maxn*2];
void ST(int n) ///这里的n是欧拉序的长度：节点个数*2-1
{///预出理出dfs序中区间里深度的最小值，并记录去到最小值的下标
    For(i,2,n) Log2[i] = Log2[i>>1]+1; ///预处理所有log2(x) x=1,2,3,...n
    For(i,1,n) Min[i][0] = i;
    for(int j=1; (1<<j)<=n; ++j)
    {
        for(int i=1;i+(1<<j)-1<=n;++i)
        {
            int a = Min[i][j-1];
            int b = Min[i+(1<<(j-1))][j-1];
            Min[i][j] = deep[a]>deep[b]?b:a;
        }
    }
}
int LCA(int x,int y)
{
    int left = First[x];
    int right = First[y];
    if(left>right) swap(left,right),swap(x,y);
    int j = Log2[right-left+1];
    int a = Min[left][j];
    int b = Min[right-(1<<j)+1][j];
    return deep[a]>deep[b]?sequence[b]:sequence[a];
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T,m,n,u,v;
    LL d;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        initG();
        For(i,1,n-1)
        {
            scanf("%d%d%lld",&u,&v,&d);
            addedge(u,v,d);
            addedge(v,u,d);
        }
        initDFS();
        dis[1] = 0;
        dfs(1,1);
        ST(2*n-1);
        while(m--)
        {
            scanf("%d%d",&u,&v);
            int lca = LCA(u,v);
            int ans = 1ll*dis[u]+dis[v]-2*dis[lca];
            printf("%d\n",ans);
        }
    }

    return 0;
}