M_sea

CF293E Close Vertices
CodeForcesLuogu分析比较简单的点分治。可是我调了好久先考虑一个简单版的题目:Tree。那道题统计答案...
扫描右侧二维码阅读全文
07
2019/05

CF293E Close Vertices

CodeForces

Luogu

分析

比较简单的点分治。可是我调了好久

先考虑一个简单版的题目:Tree

那道题统计答案是用的双指针。

但是这道题多了一个 $L$ 的限制,所以在双指针满足 $W$ 的限制的同时,再用一个树状数组来满足 $L$ 的限制就行了。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,L,W;
ll ans=0;
int sumsz,minsz,root,top;
int sz[N],vis[N],dep[N],dis[N];
pair<int,int> o[N];

struct Edge { int v,w,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

struct Bit {
    int c[N];
    inline int lowbit(int x) { return x&-x; }
    inline void add(int x,int y) {
        if (x<=0) return;
        for (;x<=n+1;x+=lowbit(x)) c[x]+=y;
    }
    inline int sum(int x) {
        if (x<=0) return 0;
        int res=0;
        for (;x;x-=lowbit(x)) res+=c[x];
        return res;
    }
} T;

inline void getroot(int u,int fa) {
    sz[u]=1; int mx=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa||vis[v]) continue;
        getroot(v,u),sz[u]+=sz[v];
        mx=max(mx,sz[v]);
    }
    mx=max(mx,sumsz-sz[u]);
    if (mx<minsz) root=u,minsz=mx;
}

inline void getdeep(int u,int fa) {
    o[++top]=make_pair(dis[u],dep[u]);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa||vis[v]) continue;
        dep[v]=dep[u]+1,dis[v]=dis[u]+w; getdeep(v,u);
    }
}

inline ll calc(int u,int dis_,int dep_) {
    top=0,dis[u]=dis_,dep[u]=dep_; getdeep(u,0);
    sort(o+1,o+top+1);
    ll res=0;
    for (re int i=1;i<=top;++i) T.add(o[i].second+1,1);
    re int i=1,j=top;
    while (i<j) {
        if (o[i].first+o[j].first<=W) {
            T.add(o[i].second+1,-1);
            res+=T.sum(L-o[i].second+1);
            ++i;
        }
        else {
            T.add(o[j].second+1,-1);
            --j;
        }
    }
    T.add(o[i].second+1,-1);
    return res;
}

inline void solve(int u) {
    ans+=calc(u,0,0),vis[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (vis[v]) continue;
        ans-=calc(v,w,1);
        sumsz=sz[v],minsz=n,getroot(v,0); solve(root);
    }
}

int main() {
    n=read(),L=read(),W=read();
    for (re int i=2;i<=n;++i) {
        int v=read(),w=read();
        addEdge(i,v,w),addEdge(v,i,w);
    }
    sumsz=minsz=n,getroot(1,0); solve(root);
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 05 月 07 日 09 : 32 PM

发表评论