@[ArachnidaKing](/space/show?uid=108024) 6666.
# 你 状压 你自己
by yijan @ 2018-12-08 08:43:33
>有趣的是**典型的**状压DP题三页题解没有一篇状压DP···QAQ
by yijan @ 2018-12-08 08:44:55
@[yijan](/space/show?uid=63398) QAQ黑历史
by ArachnidaKing @ 2018-12-08 08:47:55
$hahaha$
by hanjicheng @ 2018-12-08 08:48:29
~~你 D 你 自 己~~
by RiverFun @ 2018-12-08 08:54:57
$6_{666666}$
by HenryHuang @ 2018-12-08 09:13:19
6 66 666 6666 666 66 6
by 哦，天哪 @ 2018-12-08 09:38:31
所以两篇讨论其实是同一个主题，都是批判luogu恶意评标签 qwq
by Prurite @ 2018-12-08 09:44:00
@[星烁晶熠辉](/space/show?uid=54160) 不，第一篇是，第二篇是吐槽自己的记性，自己发的讨论都不认识……
by ArachnidaQueen @ 2018-12-08 18:42:27
我这个蒟蒻：啊？这题不是一道二分题吗（逃
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=100005;
int n,s,ans;
int r[N];
int sum,h[N];
struct Edge
{
int v,nxt;
} e[N];
void adde(int x,int y)
{
sum++;
e[sum].v=y;
e[sum].nxt=h[x];
h[x]=sum;
}
int dp[N];
void solve(int x)
{
int l=1,r=x-1,mid=(l+r)>>1,now;
while(l<=r)
{
mid=(l+r)>>1;
if(dp[x]-dp[mid]>=s)
{
now=dp[x]-dp[mid];
if(now==s) ans++;
l=mid+1;
}
else r=mid-1;
}
//if(now==s) ans++;
/*for(int i=1;i<=x-1;i++)
if(dp[x]-dp[i]==s) ans++;*/
}
void dfs(int x,int d)
{
dp[d]=dp[d-1]+r[x];
if(dp[d]==s) ans++;
else if(dp[d]>s) solve(d);
for(int i=h[x];i;i=e[i].nxt)
dfs(e[i].v,d+1);
}
int main()
{
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++) scanf("%d",r+i);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
adde(x,y);
}
dfs(1,1);
printf("%d\n",ans);
return 0;
}
```
by salix_leaf @ 2019-01-17 10:53:47