[BZOJ2599][IOI2011]Race-树上启发式合并(dsu on tree)Race

Race

Description

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

Input

第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)

Output

一个整数 表示最小边数量 如果不存在这样的路径 输出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

2

想必从搜索引擎的视角上看，这篇博客被“点分治”包围了……
毕竟做这题一开始就是为了练习点分治

思路:
让咱们先放下点分治。

可以发现，每一条路径只会有两种形状:

1.  /    2.   /
   /         /  
  /         /    

假如咱在每个节点处维护了一个桶，以权值和为下标，记录着从这个点往下走的所有路径中，每种权值和最少需要的边数。（显然是个map而不是真正的桶）

对于第一种，建出$f$后直接用$f[k]$更新即可。

考虑第二种，以及如何构建$f$:
现在假如咱们考虑到了节点$u$，它的儿子们为$v$，它的桶为$f$。

考虑按顺序加入每个儿子，先暴力一点:
对于每个儿子的子树中的点，计算出其到$u$的相对带权距离$d_w$及深度差$d$，并用$d$与$f[k-d_w]$的和来更新答案。
然后用刚才遍历到的每个$d_w$对应的$d$来更新$f[d_w]$的值。
这样就相当于，对于每个儿子内的点到$u$的链，咱们用与之带权距离和恰为$k$的，之前遍历过的另一条链与它一起，拼成一条路径并更新答案。然后，再把它们自己也加入桶中等待后面的子树被匹配。

可以发现这是$O(n^2)$的（用map加个log），而且空间复杂度不敢想象……

考虑优化。
有一种方法叫做启发式合并，其中的树上版叫$dsu on tree$。
核心思想是，对于每个点，继承其重儿子的桶以保证复杂度。
这样做能保证在暴力遍历轻儿子以更新的情况下，复杂度为$O(nlog_2n)$。

对于这题，也可以这么做:
记两个增量$offset[u]$和$delta[u]$，分别表示当前节点相对于当前重链的链底的带权距离和距离。这能通过简单的回溯操作计算。

在全局开一个桶（其实是map）$f$。
每到一个节点，优先递归其轻儿子，最后递归重儿子。
每次结束一个节点的递归时，如果这个点是轻儿子，则清空$f$，否则不做出操作
那么当回溯回当前节点时，$f$中存放着重儿子的信息。

先更新好两个增量。
于是在更新和查询时，下标值统一减去$offset[u]$，$f$内部的值则在查询时加上$delta[u]$，更新时减去$delta[u]$。
可以发现这样即可实现$O(1)$继承重儿子。
对于轻儿子，同$O(n^2)$做法相同处理即可。

考虑到每次查询和修改都是$O(log_2n)$，于是这么做复杂度为$O(nlog_2^2n)$

复杂度和点分治貌似相同？
还用了奇慢无比的STL……
然而这个不仅挺快还很短很好写……
毕竟思路这么简单粗暴
目前咱的代码在BZOJ上排名第17~
虽然习惯性的卡了一波常

#include<iostream>
#include<tr1/unordered_map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;
using namespace std::tr1;

#ifndef _WIN64
#define getchar getchar_unlocked
#endif

inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0' || '9'<ch)ch=getchar();
    while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
    return x;
}

typedef long long ll;
const int N=200009;
const int K=1000001;
const int Inf=2e9+7;

int n,k;
int to[N<<1],nxt[N<<1],w[N<<1],beg[N],tot;
int fa[N],siz[N],fae[N],son[N],dis[N],seg[N],dfn;
int id[N],ed[N],ans,offset[N],delta[N];
ll dep[N];
unordered_map<ll,int> f;

inline void add(int u,int v,int c)
{
    to[++tot]=v;
    nxt[tot]=beg[u];
    w[tot]=c;
    beg[u]=tot;
}

inline void chkmin(int &a,int b){if(a>b)a=b;}

inline void dfs_pre(int u)
{
    seg[id[u]=++dfn]=u;
    siz[u]=1;son[u]=0;
    for(register int i=beg[u],v;i;i=nxt[i])
        if((v=to[i])!=fa[u])
        {
            fa[v]=u;
            dis[v]=dis[u]+1;
            dep[v]=dep[u]+(fae[v]=w[i]);
            dfs_pre(v);
            siz[u]+=siz[v];
            if(!son[u] || siz[v]>siz[son[u]])
                son[u]=v;
        }
    ed[u]=dfn;
}

inline void dfs(int u)
{
    if(!son[u])
    {
        offset[u]=0;
        delta[u]=0;
        return;
    }

    for(register int i=beg[u],v;i;i=nxt[i])
        if((v=to[i])!=fa[u] && v!=son[u])
            dfs(v);
    dfs(son[u]);

    int &dlt=delta[u],&ofs=offset[u];
    ofs=offset[son[u]]+fae[son[u]];
    dlt=delta[son[u]]+1;

    if(f.count(f[fae[son[u]]-offset[u]]))
        chkmin(f[fae[son[u]]-offset[u]],1-dlt);
    else
        f[fae[son[u]]-offset[u]]=1-dlt;

    register ll tmp;
    for(register int i=beg[u],v;i;i=nxt[i])
        if((v=to[i])!=fa[u] && v!=son[u])
        {
            for(register int j=id[v];j<=ed[v];j++)
                if((tmp=(k-(dep[seg[j]]-dep[u])))>0 && f.count(tmp-ofs))
                    chkmin(ans,f[tmp-ofs]+dis[seg[j]]-dis[u]+dlt);
            for(register int j=id[v];j<=ed[v];j++)
                if((tmp=dep[seg[j]]-dep[u])<=k)
                {
                    if(f.count(tmp-ofs))
                        chkmin(f[tmp-ofs],dis[seg[j]]-dis[u]-dlt);
                    else
                        f[tmp-ofs]=dis[seg[j]]-dis[u]-dlt;
                }
        }

    if(f.count(k-ofs))
        chkmin(ans,f[k-ofs]+dlt);
    if(son[fa[u]]!=u && u!=1)
        f.clear();
}

int main()
{
    n=read();k=read();
    for(int i=1,u,v,w;i<n;i++)
    {
        u=read()+1;v=read()+1;w=read();
        add(u,v,w);add(v,u,w);
    }

    dfs_pre(1);
    ans=1e9+7;
    dfs(1);

    printf("%dn",ans==(int)(1e9+7)?-1:ans);
    return 0;
}

最后

以上就是闪闪蚂蚁为你收集整理的[BZOJ2599][IOI2011]Race-树上启发式合并(dsu on tree)Race的全部内容，希望文章能够帮你解决[BZOJ2599][IOI2011]Race-树上启发式合并(dsu on tree)Race所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。