P3066 [USACO12DEC]逃跑的BarnRunning Away From

题目
思路
错误&&注意
代码

题目

思路

虽说这个题目有多种做法，但

左偏树算法:

我们发现这个合并的时候并不好合并，因为存的值不是固定的

那我们是不是可以lazy数组呢

因为是两个颗树合并，显然是步阔以的

那就转换一下思路，什么是固定的呢

那就是1到i的路径

我们可以dfs出val[i]表示1到i的路径和

这个val也就是左偏树的初始值

然后我们发现，一个树i的所有后代x

都要经过1到i的所经过的路径

所以直接维护val，只需要在比较的时候减去val[i]即可

感觉我说的太恶心了，还是去看代码吧

错误&&注意

这个空间和long long让我wrong了4次，小心点吧

代码

// luogu-judger-enable-o2

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int maxn=200007;

typedef long long ll;

inline ll read() {

    ll x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return  x*f;

}

struct edge {

    int v,nxt;

    ll q;

}e[maxn<<1];

int head[maxn<<1],tot;

void add_edge(int u,int v,ll q) {

    e[++tot].v=v;

    e[tot].q=q;

    e[tot].nxt=head[u];

    head[u]=tot;

}

int n;

ll m,val[maxn];

int ans[maxn],size[maxn];

int ch[maxn][2],dis[maxn];

int merge(int x,int y) {

    if(!x||!y) return x+y;

    if(val[x]<val[y]) swap(x,y);

    ch[x][1]=merge(ch[x][1],y);

    if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]);

    dis[x]=dis[ch[x][1]]+1;

    return x;

}

int work1(int x,int y) {

    int tmp=merge(x,y);

    y=x^y^tmp;

    x=tmp;

    size[x]+=size[y];

    return tmp;

}

int work2(int x) {

    int tmp=merge(ch[x][0],ch[x][1]);

    size[tmp]=size[x]-1;

    return tmp;

}

int dfs(int u,int f) {

    ans[u]=1;

    int rt=u;

    for(int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v;

        if(v==f) continue;

        int tmp=dfs(v,u);

        rt=work1(rt,tmp);

    }

    while(val[rt]-val[u] > m) rt=work2(rt);

    ans[u]=size[rt];

    return rt;

}

void nb_dfs(int u,int f) {

    size[u]=1;

    for(int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v;

        if(v==f) continue;

        val[v]=val[u]+e[i].q;

        nb_dfs(v,u);

    }

}

int main() {

    n=read(),m=read();

    FOR(i,2,n) {

        int x=read();

        ll y=read();

        add_edge(i,x,y);

        add_edge(x,i,y);

    }

    nb_dfs(1,0);

    dfs(1,0);

    FOR(i,1,n) cout<<ans[i]<<"\n";

    return  0;

}

巴特西

P3066 [USACO12DEC]逃跑的BarnRunning Away From

题目

思路

错误&&注意

代码

最新文章

热门文章