HDU2586 How far away ？

一、描述

　　很久没写代码了，在之前一直在参与准备ASC比赛和美赛，现在又重新捡起来。目标是两个月后的邀请赛。

　　这题是树链拋分解决LCA问题的一个模板题。

　　首先介绍下树链拋分的基本思想。

对于任意一颗树，定义重链为自上走到下，经历的节点数量最多的一条路径。定义轻链为其他链。
每个节点都属于一个重链。如果节点本身不在父节点所在的重链上，那么说他一定是一条新的重链的顶端。
对于任意节点，采取每次都直接跳到重链顶端的方式，最多logn次可以跳到树根。（下述循环最多执行LOGN）
```
while(now!=root)

{

        if(now==top[now])now=father[now];

        now=top[now];

}
```

对于每两个不同的节点，最多跳LOGN次可以使得两个节点走到同一条重链上，在跳跃的时候进行分级跳跃，即定义重链的级别（在祖先节点所经历的重链的条数）。于是跳跃函数如下：

ll query(ll a,ll b)

{

    ll ret=;

    while(top[a]!=top[b])

    {

        if(depth[a]<depth[b])

        {

            jump(b,ret);

        }else jump(a,ret);

    }

    ret+=abs(top_dis[a]-top_dis[b]);

    return ret;

}

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pp pair <ll,ll>

#define veci vector<ll>

#define vecp vector<pp>

const ll MAXN=;

ll depth[MAXN];

ll fa[MAXN];

ll dis[MAXN];

ll top_dis[MAXN];

ll child[MAXN];

ll top[MAXN];

vecp path[MAXN];

ll n,m;

void dfs(ll now,ll father)

{

    fa[now]=father;

    child[now]=;

    ll len=path[now].size();

    for(ll i=;i<len;++i)

    {

        ll tar=path[now][i].first;

        ll val=path[now][i].second;

        if(tar==father)continue;

        dis[tar]=val;

        dfs(tar,now);

        child[now]+=child[tar];

    }

    child[now]++;

}

void build_tree(ll now,ll to,ll dep,ll length)

{

    top[now]=to;

    depth[now]=dep;

    top_dis[now]=length;

    ll len=path[now].size();

    ll maxx=;

    ll node=;

    for(ll i=;i<len;++i)

    {

        ll tar=path[now][i].first;

        ll val=path[now][i].second;

        if(tar==fa[now])continue;

        node = maxx < child[tar] ? i : node;

        maxx=max(maxx,child[tar]);

    }

    for(ll i=;i<len;++i)

    {

        ll tar=path[now][i].first;

        ll val=path[now][i].second;

        if(tar==fa[now])continue;

        if(i==node)    build_tree(tar,to,dep,length+val);

        else build_tree(tar,tar,dep+,);

    }

}

ll jump(ll &now,ll &ret)

{

    ret+=top_dis[now];

    now=top[now];

    ret+=dis[now];

    now=fa[now];

    return now;

}

ll query(ll a,ll b)

{

    ll ret=;

    while(top[a]!=top[b])

    {

        if(depth[a]<depth[b]) jump(b,ret);

        else jump(a,ret);

    }

    ret+=abs(top_dis[a]-top_dis[b]);

    return ret;

}

void init()

{

    cin>>n>>m;

    for(ll i=;i<=n;++i)path[i].clear();

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

    {

        ll a,b,c;

        cin>>a>>b>>c;

        path[a].push_back(make_pair(b,c));

        path[b].push_back(make_pair(a,c));

    }

    dfs(,);

    build_tree(,,,);

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

    {

        ll a,b;cin>>a>>b;

        cout<<query(a,b)<<"\n";

    }

}

int main()

{

    cin.sync_with_stdio(false);

    ll t;

    cin>>t;

    for(ll i=;i<t;++i)init();

    return ;

}

logn

HDU2586 How far away ？

一、描述