题解 P4183 【[USACO18JAN]Cow at Large P】

y2823774827y · 2019-03-01 11:56:16 · 题解

感觉楼下写的有点不清楚，反正我看不懂，这么说dalao是不是有点不好

显然，g_i为i到最近叶子节点的距离，d_i为i的度数

假设我们要求的是ans_u，如果把u作为根，dep_i≥g_i则i这棵子树贡献为1就能拦截u，但为了保证唯一性，dep_i≥g_i \&\& dep_{fa_{i}}<g_{fa_{i}}

时间复杂度O(n^2)

点对贡献，考虑用点分治优化

对于一棵子树，\sum\limits^m d_i=2m-1,\therefore 1=\sum\limits^m (2-d_i)，根据子树贡献单调性，ans_u=\sum\limits_{i=1}^n [dis(u,i)≥g_i](2-d_i)

至此，该题转换成点分治模板题，时间复杂度O(nlog^2n)

乱七八糟的代码：

#include<bits/stdc++.h>
using namespace std;
typedef int LL;
const LL maxn=1e5,inf=0x3f3f3f3f;
struct node{
    LL to,nxt;
}dis[maxn<<1];
LL n,root,num,up,N,mi,tim;
LL ans[maxn],head[maxn],d[maxn],g[maxn],tree[maxn],visit[maxn],size[maxn],V[maxn];
inline void Add(LL u,LL v){
    dis[++num]=(node){v,head[u]}, head[u]=num;
    ++d[v];
}
void Dfs1(LL u,LL f){
    if(d[u]==1) g[u]=0;
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(v==f) continue;
        Dfs1(v,u);
        g[u]=min(g[u],g[v]+1);
    }
}
void Dfs2(LL u,LL f){
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(v==f) continue;
        g[v]=min(g[v],g[u]+1);
        Dfs2(v,u);
    }
}

inline LL Lowbit(LL x){ return x&-x; }
inline LL Query(LL x){ LL ret(0); x+=up; for(;x;x-=Lowbit(x)) ret+=tree[x]; return ret; }
inline void Modify(LL x,LL val){ x+=up; for(;x<=100000;x+=Lowbit(x)) tree[x]+=val; }
void Dfs(LL u){
    LL mx(0); visit[u]=true; size[u]=1;
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(visit[v]) continue;
        Dfs(v); size[u]+=size[v];
        mx=max(mx,size[v]);
    }mx=max(mx,N-size[u]);
    if(mi>mx) mi=mx,root=u;
    visit[u]=false;
}
void Get(LL u,LL dt){
    ans[u]+=Query(dt);
    visit[u]=true;
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(visit[v]) continue;
        Get(v,dt+1);
    }visit[u]=false;
}
void Up(LL u,LL dt){
    Modify(g[u]-dt,2-d[u]);
    visit[u]=true;
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(visit[v]) continue;
        Up(v,dt+1);
    }visit[u]=false;
}
void Clear(LL u,LL dt){
    Modify(g[u]-dt,-(2-d[u]));
    visit[u]=true;
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(visit[v]) continue;
        Clear(v,dt+1);
    }visit[u]=false;
}
void Div(LL u){
    mi=inf, Dfs(u); 
    u=root;
    visit[u]=true;
    LL top(0);
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(visit[v]) continue;
        V[++top]=v;
        Get(v,1);
        Up(v,1);
    }
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(visit[v]) continue;
        Clear(v,1);
    }
    Modify(g[u],2-d[u]);
    for(LL i=top;i>=1;--i){
        LL v(V[i]);
        Get(v,1);
        Up(v,1);
    }ans[u]+=Query(0);
    Modify(g[u],-(2-d[u]));
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(visit[v]) continue;
        Clear(v,1);
    }
    for(LL i=head[u],sum=N;i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(visit[v]) continue;
        N=(size[v]>size[u]?sum-size[u]:size[v]);
        Div(v);
    }
}
int main(){
    cin>>n; up=n;
    for(LL i=1;i<n;++i){
        LL u,v; cin>>u>>v;
        Add(u,v), Add(v,u);
    }
    memset(g,inf,sizeof(g));
    Dfs1(1,0), Dfs2(1,0);
    N=n; Div(1);
    for(LL i=1;i<=n;++i) if(d[i]==1) cout<<1<<endl;else cout<<ans[i]<<endl;
    return 0;
}