长链剖分学习笔记

长链剖分在去年NOIP之前就想学了，被我鸽到了现在（。

省选竟然考了啊喂（哭死虽然那个时候三个月没写代码的状态即使我会写也没救

都是小问题

长链剖分看名字就知道是类似树链剖分的一类东西

树链剖分其实是重链剖分但是是市面上流传最广的树链剖分好像大家都习惯直接称之为树链剖分...

重链剖分是按照子树重量进行剖分长链剖分就是按照子树（最长链）长度进行剖分

它的优势在于维护只与树的深度有关的信息时每条重链只在顶端合并一次因此对应上优秀的实现就是线性的复杂度

优秀的实现其实也很简单

我们第二遍dfs的时候按照先递归重链并编号，这样的话内存是连续的可以直接继承重儿子，且恰好比重儿子多一个位置，对应整条链的长度。

板子：CF1009F

本来就是EducationalRound 估计就是给大家科普这个吧？

//Love and Freedom.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define inf 20021225
#define N 1000100
using namespace std;
int read()
{
    int s=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return f*s;
}
struct edge{int to,lt;}e[N<<1];
int in[N],cnt,f[N],len[N],id[N],tms,son[N],ans[N];
void add(int x,int y)
{
    e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;
    e[++cnt].to=x; e[cnt].lt=in[y]; in[y]=cnt;
}
void dfs(int x,int fr)
{
    len[x]=1;
    for(int i=in[x];i;i=e[i].lt)
    {
        int y=e[i].to; if(fr==y)    continue; dfs(y,x);
        if(len[y]+1>len[x])    len[x]=len[y]+1,son[x]=y;
    }
}
void calc(int x,int fr)
{
    id[x]=++tms; f[id[x]]=1;// printf("%d %d\n",x,fr);
    if(son[x])    calc(son[x],x),ans[x]=ans[son[x]]+1;
    for(int i=in[x];i;i=e[i].lt)
    {
        int y=e[i].to; if(fr==y||son[x]==y)    continue;
        calc(y,x);
        for(int j=0;j<len[y];j++)
        {
            f[id[x]+j+1]+=f[id[y]+j];
            if(f[id[x]+j+1]>f[id[x]+ans[x]]||(f[id[x]+j+1]==f[id[x]+ans[x]]&&j+1<ans[x]))
                ans[x]=j+1;
        }
    }
    if(f[id[x]+ans[x]]==1)    ans[x]=0;
}
int main()
{
    int n=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add(x,y);
    }
    dfs(1,0); calc(1,0);
    for(int i=1;i<=n;i++)    printf("%d\n",ans[i]);
    return 0;
}

View Code

BZOJ3252

好像跟长链剖分没毛关系...就是个简单贪心...

类似长链剖分一样剖出长链来，但是边权代替长度，然后直接取前k项就好了。

//Love and Freedom.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define inf 20021225
#define N 200010
using namespace std;
int read()
{
    int s=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return f*s;
}
struct edge{int to,lt;}e[N<<1];
int in[N],cnt,len[N],id[N],tms,son[N],a[N];
priority_queue<ll> hp; ll f[N];
void add(int x,int y)
{
    e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;
    e[++cnt].to=x; e[cnt].lt=in[y]; in[y]=cnt;
}
void dfs(int x,int fr)
{
    for(int i=in[x];i;i=e[i].lt)
    {
        int y=e[i].to; if(y==fr)    continue; dfs(y,x);
        if(f[y]>f[x])    f[x]=f[y],son[x]=y;
    }
    f[x]+=a[x];
}
void dfs2(int x,int t,int fr)
{
    if(x==t)    hp.push(f[x]);
    if(!son[x])    return;
    dfs2(son[x],t,x);
    for(int i=in[x];i;i=e[i].lt)
    {
        int y=e[i].to; if(y==son[x]||y==fr)    continue;
        dfs2(y,y,x);
    }
}
int main()
{
    int n=read(),k=read();
    for(int i=1;i<=n;i++)    a[i]=read();
    for(int i=1;i<n;i++)    add(read(),read());
    dfs(1,0); dfs2(1,1,1); ll ans=0;
    while(k && !hp.empty())    k--,ans+=hp.top(),hp.pop();
    printf("%lld\n",ans);
    return 0;
}

View Code

想补希望，但它好像没有什么希望...

（咕咕咕）