藏宝

DP 二分

---

题面

给一棵有$n$个节点的带点权树，有$q$次询问，问如果要求一条路径上点权和小于等于$lim$,那么这条路径最多能包括多少点？

• $20pts\ n\leq100,q\leq4000$
• $60pts\ lim_i\leq20$
• $80pts\ rand$
• $100pts\ n\leq20000,q\leq2*10^6,lim_i\leq10^{17},w_i\leq10^9,dep_u\leq500$
  (下包含上）

解析

$20pts$算法

从每一个点出发，看最多能走多远。
注意存在$ans=0$的情况！！！
复杂度上限$O(qn^2)$

$60pts$算法

直接暴力$DP$。
设$g[u][k]$表示自$u$点向下，点权和为$k$时最多能向下走多远。
设$f[u][k]$表示以$u$点为根的子树中，点权和为$k$的路径最多有多长。
转移方程

$$f[u][i]=max(f[u][i],g[u][j]+g[v][i-j])$$
$$g[u][i+w[u]]=max(g[u][i+w[u]],g[v][i]+1)$$
用$ans[lim]$统计所有$f[u][lim]$最大值，就可以$O(1)$处理询问了。
复杂度$O(20^2n)$
注意：
1、对一点$f$进行$DP$时，该点$g$数组中不能包含当前子节点的贡献。
2、注意边界是叶节点$g[u][w[u]]=1$。（这玩意儿应该写在开头）
3、$ans$数组后面答案要与前面取$max$。

il void dfs(re int u,re int fa)
{
  re int flag=0;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;flag=1;
      dfs(v,u);
      fp(i,0,20) fp(j,0,i) f[u][i]=max(f[u][i],g[u][j]+g[v][i-j]);
      fp(i,0,20-w[u]) g[u][i+w[u]]=max(g[u][i+w[u]],g[v][i]+1);
    }
  if(!flag) if(w[u]<=20) g[u][w[u]]=1;
}
il void dfss(re int u,re int fa,re ll s,re int dis)
{
  if(s<=lim) ans1=max(ans1,dis);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      if(s+w[v]<=lim) dfss(v,u,s+w[v],dis+1);
    }
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();Q=gi();
  fp(i,1,n) w[i]=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi();
      add(u,v);add(v,u);
    }
  if(n<=100&&Q<=4000)
    {
  fp(i,1,Q)
    {
      ans1=0;lim=gi();
      fp(i,1,n) dfss(i,i,w[i],1);
      printf("%lld\n",ans1);
    }
  return 0;
    }
  dfs(1,0);
  fp(i,0,20) fp(j,1,n) ans[i]=max(ans[i],f[j][i]);
  fp(i,1,20) ans[i]=max(ans[i],ans[i-1]);
  while(Q--)
    {
      printf("%lld\n",ans[gi()]);
    }
  return 0;
}

$80pts$算法

随机数据等价于$maxdeep\leq2*logn$
有一个套路：
如果一个$dp$数组，状态范围大而结果范围小，可以将结果与状态交换位置。
于是我们可以把$f[u][k]$表示的状态改为以$u$点为根的子树中，包含点数为$k$的路径需要的最小点权和。$g[u][k]$同理。
转移差不多。并且由于$f$数组不需要上传，$u$这一维实际上可以省掉。
这样就可以处理$lim$很大的情况了。
当然，询问时，由于链长越大需要的点权和也越大，符合单调性，可以二分答案。
复杂度$O(40^2n+Qlogn)$左右。

$100pts$算法

树高很大。
复杂度可以达到$O(500^2n)$，会$GG$的。
然而每个点枚举链长时，不一定要枚到$500$。不是每个点下面都有$500$个点。
于是只要枚到该点离自己子树下叶节点最远距离即可。
复杂度？玄学。。。反正能过。

注意一下二分时，判断条件应该是合法或不合法，不能两者混杂。
比如说不能写成

 while(l<=r)
    {
      re ll mid=l+r>>1;
      if(f[mid]>=lim) ans=mid,r=mid-1;
      else l=mid+1;
    }

还有鬼知道为什么数据会有答案大于$1000$的。。。
其实是出题人认为树根深度为$0$。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e4+100;
struct Edge{int to,nxt;}e[N<<1];
ll w[N],n,h[N],cnt,Q,lim,ans;
ll f[2005],g[N][1005],d[N];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dfs(re int u,re int fa)
{
  d[u]=1;g[u][0]=0;g[u][1]=w[u];
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u);
      fp(i,0,d[u]) fp(j,0,d[v]) f[i+j]=min(f[i+j],g[u][i]+g[v][j]);
      d[u]=max(d[u],d[v]+1);
      fp(i,1,d[u]) g[u][i]=min(g[u][i],g[v][i-1]+w[u]);
    }
}
int main()
{
  freopen("erusaert.in","r",stdin);
  freopen("erusaert.out","w",stdout);
  memset(h,-1,sizeof(h));memset(f,63,sizeof(f));memset(g,63,sizeof(g));
  n=gi();Q=gi();
  fp(i,1,n) w[i]=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi();
      add(u,v);add(v,u);
    }
  dfs(1,0);
  while(Q--)
    {
      lim=gi();
      re ll l=0,r=2000,ans=0;
      while(l<=r)
    {
      re ll mid=l+r>>1;
      if(f[mid]<=lim) ans=mid,l=mid+1;
      else r=mid-1;
    }
      printf("%lld\n",ans);
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}