题目链接

思路

点分治。

（题面居然不说询问的最大值为106）

Naive的O(qnlog2n)算法(1)：

对每次询问做一遍点分治，用two pointer查询v1+v2<=k且v1+v2>k的v1,v2的个数，加上排序单次查询就是O(nlogn)。

BZOJ会TLE吧。

常数大了点的O(qnlogn)算法(2)：

对每次询问做一遍点分治，用一个桶记录值为v1的个数，然后查询一下q−v2的值的个数。

BZOJ还是会TLE。

常数比较小的O(qnlogn)算法(3)：

在算法(2)的基础上，离线回答询问，不用对每次询问做一遍点分治，只需要总体上做一遍点分治就可以了。

BZOJ 1000ms AC。

O(n2logn)算法(4)：

把所有路径长度都丢到桶里面，最后O(1)回答询问。

BZOJ 4000ms以上 AC。

代码

特别感谢yxc大佬的算法(1),(4)的代码

算法(1)

#include
    
     #include
     
      #define il inline#define rg register#define N 10001using namespace std;struct fk{
   int to,w,nxt;}e[N<<1];int n,k,p,root,Max,ans,dis[N],top;int sz[N],maxv[N],head[N],cnt,vis[N];il int read(){    char ch=getchar();int x=0,f=1;    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+ch-'0';    return x*f;}il void add(int u,int v,int w){e[++cnt].to=v;e[cnt].nxt=head[u];e[cnt].w=w;head[u]=cnt;}il void get_size(int u,int fa){    sz[u]=1;maxv[u]=0;    for(rg int i=head[u];i;i=e[i].nxt)        if(e[i].to!=fa&&!vis[e[i].to])get_size(e[i].to,u),sz[u]+=sz[e[i].to],maxv[u]=max(maxv[u],sz[e[i].to]);}il void get_root(int r,int u,int fa){    maxv[u]=max(maxv[u],sz[r]-sz[u]);    if(Max>maxv[u])Max=maxv[u],root=u;    for(rg int i=head[u];i;i=e[i].nxt)        if(e[i].to!=fa&&!vis[e[i].to])get_root(r,e[i].to,u);}il void get_dis(int u,int fa,int d){    dis[++top]=d;    for(rg int i=head[u];i;i=e[i].nxt)        if(e[i].to!=fa&&!vis[e[i].to])get_dis(e[i].to,u,d+e[i].w);}il int calc(int rt,int d){    top=0;get_dis(rt,0,d);    sort(dis+1,dis+top+1);    int l=1,r=top,ret1=0,ret2=0;    while(l
      
       k&&l
       
        =k&&l
        
         0?"Yes\n":"No\n");        for(rg int i=1;i<=n;i++)vis[i]=0;ans=0;    }}

算法(2)

#include 
    
     #include 
     
      #include 
      
       const int maxn=10000;const int maxp=100;const int maxv=1000000;const int inf=0x3f3f3f3f;int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}int pre[maxn*2+10],now[maxn+10],son[maxn*2+10],tot,val[maxn*2+10];int vis[maxn+10],f[maxn+10],size[maxn+10],n,p,bin[maxv+10];int q,nowroot,nowsize,cnt,tmp[maxn+10],flag,deep[maxn+10];int ins(int a,int b,int c){  pre[++tot]=now[a];  now[a]=tot;  son[tot]=b;  val[tot]=c;  return 0;}int getc(int u,int fa){  size[u]=1;  f[u]=0;  int j=now[u];  while(j)    {      int v=son[j];      if((v!=fa)&&(!vis[v]))        {          getc(v,u);          size[u]+=size[v];          f[u]=std::max(f[u],size[v]);        }      j=pre[j];    }  f[u]=std::max(f[u],nowsize-size[u]);  if(f[u]
       
        =tmp[i])        {          res+=bin[q-tmp[i]];        }    }  return res>>1;}int solve(int u){  vis[u]=1;  int ans=calc(u,0),j=now[u];  while(j)    {      int v=son[j];      if((!vis[v])&&(!flag))        {          ans-=calc(v,val[j]);          nowroot=0;          nowsize=size[v];          getc(v,0);          solve(nowroot);        }      j=pre[j];    }  if(ans>0)    {      flag=1;    }  return 0;}int main(){  n=read();  p=read();  for(int i=1; i

算法(3)

#include 
    
     #include 
     
      #include 
      
       const int maxn=10000;const int maxp=100;const int maxv=1000000;const int inf=0x3f3f3f3f;int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}int pre[maxn*2+10],now[maxn+10],son[maxn*2+10],tot,val[maxn*2+10];int vis[maxn+10],f[maxn+10],size[maxn+10],n,p,bin[maxv+10];int q[maxn+10],ans[maxn+10],nowroot,nowsize,cnt,tmp[maxn+10],flag,deep[maxn+10];int ins(int a,int b,int c){  pre[++tot]=now[a];  now[a]=tot;  son[tot]=b;  val[tot]=c;  return 0;}int getc(int u,int fa){  size[u]=1;  f[u]=0;  int j=now[u];  while(j)    {      int v=son[j];      if((v!=fa)&&(!vis[v]))        {          getc(v,u);          size[u]+=size[v];          f[u]=std::max(f[u],size[v]);        }      j=pre[j];    }  f[u]=std::max(f[u],nowsize-size[u]);  if(f[u]
       
        maxv)    {      return 0;    }  tmp[++cnt]=deep[u];  int j=now[u];  while(j)    {      int v=son[j];      if((v!=fa)&&(!vis[v]))        {          deep[v]=deep[u]+val[j];          getdeep(v,u);        }      j=pre[j];    }  return 0;}int calc(int u,int ud,int op){  deep[u]=ud;  cnt=0;  getdeep(u,0);  for(int i=1; i<=cnt; ++i)    {      ++bin[tmp[i]];    }  for(int k=1; k<=p; ++k)    {      int nq=q[k],res=0;      for(int i=1; i<=cnt; ++i)        {          if(nq>=tmp[i])            {              res+=bin[nq-tmp[i]];              if(nq==(tmp[i]<<1))                {                  ++res;                }            }        }      ans[k]+=op*(res>>1);    }  for(int i=1; i<=cnt; ++i)    {      --bin[tmp[i]];    }  return 0;}int solve(int u){  vis[u]=1;  calc(u,0,1);  int j=now[u];  while(j)    {      int v=son[j];      if(!vis[v])        {          calc(v,val[j],-1);          nowroot=0;          nowsize=size[v];          getc(v,0);          solve(nowroot);        }      j=pre[j];    }  return 0;}int main(){  n=read();  p=read();  for(int i=1; i
        
         0))        {          puts("Yes");        }      else        {          puts("No");        }    }  return 0;}

算法(4)

#include
    
     #include
     
      #include
      
       #define il inline#define rg register#define N 10001using namespace std;struct fk{
   int to,w,nxt;}e[N<<1];int n,k,p,root,Max,ans,dis[N],top;int sz[N],maxv[N],head[N],cnt,vis[N],sum[1000001];il int read(){    char ch=getchar();int x=0,f=1;    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+ch-'0';    return x*f;}il void add(int u,int v,int w){e[++cnt].to=v;e[cnt].nxt=head[u];e[cnt].w=w;head[u]=cnt;}il void get_size(int u,int fa){    sz[u]=1;maxv[u]=0;    for(rg int i=head[u];i;i=e[i].nxt)        if(e[i].to!=fa&&!vis[e[i].to])get_size(e[i].to,u),sz[u]+=sz[e[i].to],maxv[u]=max(maxv[u],sz[e[i].to]);}il void get_root(int r,int u,int fa){    maxv[u]=max(maxv[u],sz[r]-sz[u]);    if(Max>maxv[u])Max=maxv[u],root=u;    for(rg int i=head[u];i;i=e[i].nxt)        if(e[i].to!=fa&&!vis[e[i].to])get_root(r,e[i].to,u);}il void get_dis(int u,int fa,int d){    dis[++top]=d;    for(rg int i=head[u];i;i=e[i].nxt)        if(e[i].to!=fa&&!vis[e[i].to]&&d+e[i].w<=1e6)get_dis(e[i].to,u,d+e[i].w);}il void calc(int rt,int d,int t){    top=0;get_dis(rt,0,d);    sort(dis+1,dis+top+1);    for(int i=1;i<=top;i++)        for(int j=i+1;j<=top;j++)        {            if(dis[i]+dis[j]>1e6)break;            sum[dis[i]+dis[j]]+=t?1:-1;        }}il void dfs(int u){    Max=n;get_size(u,0);get_root(u,u,0);    int rt=root;    calc(rt,0,1);vis[rt]=1;    for(rg int i=head[rt];i;i=e[i].nxt)        if(!vis[e[i].to])calc(e[i].to,e[i].w,0),dfs(e[i].to);}int main(){    n=read(),p=read();    for(int i=1,u,v,w;i

转载于:https://www.cnblogs.com/Canopus-wym/p/10376179.html

你可能感兴趣的文章

Vue教程02：v-model、v-text、v-html

查看>>

App Store 狠抓精神文明建设，JSPatch要亡了？

查看>>

专注数据，打造阿里云Elasticsearch“一站式”数据服务体系

查看>>

一文读懂前端缓存

查看>>

script中defer和async的区别

查看>>