bzoj2783 [JLOI2012]树

Description

数列

提交文件：sequence.pas/c/cpp

输入文件：sequence.in

输出文件：sequence.out

问题描述：

把一个正整数分成一列连续的正整数之和。这个数列必须包含至少两个正整数。你需要求出这个数列的最小长度。如果这个数列不存在则输出-1。

输入格式：

每行包含一个正整数n。

每个文件包含多行，读入直到文件结束。

输出格式：

对于每个n，输出一行，为这个数列的最小长度。

第一行是两个整数N和S，其中N是树的节点数。

第二行是N个正整数，第i个整数表示节点i的正整数。

接下来的N-1行每行是2个整数x和y，表示y是x的儿子。

输出格式：

输出路径节点总和为S的路径数量。

输入样例：

输出样例：

3 3

1 2 3

1 2

1 3

数据范围：

对于30%数据，N≤100；

对于60%数据，N≤1000；

对于100%数据，N≤100000，所有权值以及S都不超过1000。

数据范围：

对于所有数据，n≤2⁶³。

这个是JLOI2012的T1，发出来仅为了试题完整

=============================================================================================

在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路径不必一定从根节点开始。

Input

第一行是两个整数N和S，其中N是树的节点数。

第二行是N个正整数，第i个整数表示节点i的正整数。

接下来的N-1行每行是2个整数x和y，表示y是x的儿子。

Output

输出路径节点总和为S的路径数量。

Sample Input

3 3
1 2 3
1 2
1 3

Sample Output

HINT

对于100%数据，N≤100000，所有权值以及S都不超过1000。

正解：$set$启发式合并。

题面鬼得不行。。

比较简单的一个题，直接在树上用启发式合并即可，我偷懒所以写了个$multiset$。。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (200010)
 6 
 7 using namespace std;
 8 
 9 struct edge{ int nt,to; }g[N<<1];
10 
11 int head[N],val[N],son[N],sz[N],rt[N],tim[N],num,n,S;
12 ll ans;
13 
14 multiset<int> st[N];
15 
16 multiset<int>:: iterator it;
17 
18 il int gi(){
19   RG int x=0,q=1; RG char ch=getchar();
20   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
21   if (ch=='-') q=-1,ch=getchar();
22   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
23   return q*x;
24 }
25 
26 il void insert(RG int from,RG int to){
27   g[++num]=(edge){head[from],to},head[from]=num; return;
28 }
29 
30 il void dfs(RG int x,RG int p){
31   sz[x]=1; RG int v,tr;
32   for (RG int i=head[x];i;i=g[i].nt){
33     v=g[i].to; if (v==p) continue;
34     dfs(v,x),sz[x]+=sz[v];
35     if (sz[son[x]]<=sz[v]) son[x]=v;
36   }
37   if (val[x]==S) ++ans;
38   if (!son[x]){ rt[x]=x,st[x].insert(val[x]); return; }
39   rt[x]=rt[son[x]],tim[rt[x]]+=val[x],tr=rt[x];
40   ans+=st[tr].count(S-tim[tr]);
41   for (RG int i=head[x],Rt,d;i;i=g[i].nt){
42     v=g[i].to; if (v==p || v==son[x]) continue; Rt=rt[v];
43     for (it=st[Rt].begin();it!=st[Rt].end();++it){
44       d=(*it)+tim[Rt]+val[x]; if (d==S) ++ans;
45       if (d<=S) st[tr].insert(d-tim[tr]);
46     }
47     st[Rt].clear();
48   }
49   st[tr].insert(val[x]-tim[tr]); return;
50 }
51 
52 int main(){
53 #ifndef ONLINE_JUDGE
54   freopen("tree.in","r",stdin);
55   freopen("tree.out","w",stdout);
56 #endif
57   n=gi(),S=gi();
58   for (RG int i=1;i<=n;++i) val[i]=gi();
59   for (RG int i=1,x,y;i<n;++i)
60     x=gi(),y=gi(),insert(x,y),insert(y,x);
61   dfs(1,0),cout<<ans; return 0;
62 }