蒟蒻初学 淀粉质,有点自闭

P3806 【模板】点分治 1

Provicy @ 2020-01-15 10:06:05

#include <bits/stdc++.h>
#define ri register
#define inf 0x3f3f3f3f
using namespace std; const int N=20010;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar(); return s*w;
}
int n,m,size[N],dis[N],book[N],ans,root,maxx,K,cnt=1;
int head[N],maxE; struct Edge{int nxt,to,rdis;}e[N];
inline void Add(int u,int v,int w) {e[++maxE].nxt=head[u]; head[u]=maxE; e[maxE].to=v; e[maxE].rdis=w; }
void FindRoot(int x,int fa,int S)
{
    int cs=-inf; size[x]=1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(e[i].to==fa||book[e[i].to]) continue;
        FindRoot(e[i].to,x,S);
        size[x]+=size[e[i].to];
        cs=max(cs,size[e[i].to]);
    }
    cs=max(cs,S-size[x]);
    if(cs<maxx) maxx=cs, root=x;
}
void Dis(int x,int fa,int val)
{
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(e[i].to==fa||book[e[i].to]) continue;
        dis[++cnt]=val+e[i].rdis;
        Dis(e[i].to,x,val+e[i].rdis);
    }
}
inline int Get_L(int l,int val)
{
    int r=cnt, rss=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(dis[mid]<=val) rss=mid, l=mid+1;
        else r=mid-1;
    }
    return rss;
}
inline int Get_R(int l,int val)
{
    int r=cnt, rss=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(dis[mid]<val) l=mid+1;
        else rss=mid, r=mid-1;
    }
    return rss;
 } 
int Ans(int x,int val)
{
    cnt=1; dis[cnt]=val;
    Dis(root,0,val);
    sort(dis+1,dis+1+cnt);
    int p=1, res=0;
    while(p<cnt&&dis[cnt]+dis[p]<K) p++;
    while(p<cnt&&(dis[p]<<1)<=K)
    {
        int L=Get_R(p+1,K-dis[p]), R=Get_L(p+1,K-dis[p]);
        if(R>=L) res+=R-L+1; p++;
    }
    return res;
}
void Solve(int x)
{
    book[x]=1; ans+=Ans(x,0); printf("%d\n",ans);
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(book[e[i].to]) continue;
        ans-=Ans(e[i].to,e[i].rdis);
        printf("%d\n",ans);
        root=0; maxx=inf;
        FindRoot(e[i].to,x,size[e[i].to]);
        Solve(root);
    }
}
int main()
{
    n=read(), m=read();
    for(ri int i=1;i<n;i++)
    {
        int u,v,w; u=read(), v=read(), w=read();
        Add(u,v,w), Add(v,u,w);
    }
    for(ri int i=1;i<=m;i++)
    {
        K=read(); ans=root=0; maxx=inf;
        FindRoot(1,0,n); Solve(root);
        memset(book,0,sizeof(book));
        ans?puts("AYE"):puts("NAY");
    }
    return 0;
}

40 分 WA 了,第一个点都没过,自闭了qaq


by Provicy @ 2020-01-15 10:06:29

中间的输出是调试用的,不必在意


by x义x @ 2020-01-15 10:06:45

前排 % 点分治神 ZK


by Karry5307 @ 2020-01-15 10:13:37

@DXL 前排 % 点分治神 ZK


by Provicy @ 2020-01-15 10:14:49

@Karry5307 ???fAKe 行为


by Provicy @ 2020-01-15 10:16:22

完了,我又眼瞎了,咋办啊/dk,昨天晚上也眼瞎


by x义x @ 2020-01-15 10:16:41

@DXL sto 神 ZK 爆切点分治


by Karry5307 @ 2020-01-15 10:22:31

@DXL 我 tm 萌萌哒那题 <= 写 == 然后一看 tm 草草草


by 辰星凌 @ 2020-01-15 10:44:00

Orz 淀粉质巨捞


by FZzzz @ 2020-01-15 10:48:52

前排 % 点分治神 ZK


by caidzh @ 2020-01-15 11:11:19

@DXL sto 神 ZK 爆切点分治

不过讲真你这个点分治复杂度是假的呢/xk


| 下一页