[NOIp2017复习]一些树有关的题

  1. NOIP2016 Day1T2 天天爱跑步
  2. NOIP2015 Day2T3 运输计划
  3. NOIP2013 Day1T3 货车运输
  4. NOIP2012 Day2T3 疫情控制
  5. NOIP2014 Dau1T2 联合权值

    基本不是什么很好写的题

所以还是练下暴力分姿势吧.天天爱跑步的暴力分打满还是挺多的(虽然暴力分打满基本就能想出来了)

ARC083E - Bichrome Tree


Time limit : 2sec / Memory limit : 256MB
Score : 700 points

Problem Statement

We have a tree with $N$ vertices. Vertex 1 is the root of the tree, and the parent of Vertex $i$ ($2≤i≤N$) is Vertex $P_i$.
To each vertex in the tree, Snuke will allocate a color, either black or white, and a non-negative integer weight.
Snuke has a favorite integer sequence, $X_1$,$X_2$,…,$X_N$, so he wants to allocate colors and weights so that the following condition is satisfied for all $v$.

  • The total weight of the vertices with the same color as $v$ among the vertices contained in the subtree whose root is $v$, is $X_v$.

Here, the subtree whose root is $v$ is the tree consisting of Vertex $v$ and all of its descendants.

Determine whether it is possible to allocate colors and weights in this way.

Constraints

  • $1≤N≤1000$
  • $1≤P_i≤i−1$
  • $0≤X_i≤5000$

Inputs

Input is given from Standard Input in the following format:

1
2
3
N
P2 P3 … PN
X1 X2 … XN

Outputs

If it is possible to allocate colors and weights to the vertices so that the condition is satisfied, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

1
2
3
3
1 1
4 3 2

Sample Output 1

1
POSSIBLE

For example, the following allocation satisfies the condition:

  • Set the color of Vertex 1 to white and its weight to 2.
  • Set the color of Vertex 2 to black and its weight to 3.
  • Set the color of Vertex 3 to white and its weight to 2.

There are also other possible allocations.

Sample Input 2

1
2
3
3
1 2
1 2 3

Sample Output 2

1
IMPOSSIBLE

If the same color is allocated to Vertex 2 and Vertex 3, Vertex 2 cannot be allocated a non-negative weight.

If different colors are allocated to Vertex 2 and 3, no matter which color is allocated to Vertex 1, it cannot be allocated a non-negative weight.

Thus, there exists no allocation of colors and weights that satisfies the condition.

题解

题目地址http://arc083.contest.atcoder.jp/tasks/arc083_c

题意:

$n$ 个点, $1$ 为根节点然后读入第 $2$~$n$ 个点的父节点

$n$ 个数字 $X_i$,要求给每个点赋予黑色或白色和权值,满足对于每个点 $v$,子树$v$中和$v$同色的点的权值和等于$X_v$。每个点的点权任意.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=2e3+100;
int n,X;
int to[maxn<<1],ne[maxn<<1],po[maxn],id;
int dp[2][6000],d[maxn];
int a[maxn],b[maxn];
inline void add(int x,int y)
{
id++;
to[id]=y;ne[id]=po[x];po[x]=id;
}
bool dfs(int x,int fa)
{
int y;
if (d[x]==1&&x!=1) return true;
for (int i=po[x];i;i=ne[i])
{
y=to[i];
if (y==fa) continue;
if (!dfs(to[i],x)) return false;
}//先把子树扫完
memset(dp,0,sizeof(dp));
dp[0][0]=1;
int cur=0,sum=0;
for (int i=po[x];i;i=ne[i])
{
y=to[i];
if (y==fa) continue;
cur^=1;
memset(dp[cur],0,sizeof(dp[cur]));
sum+=a[y]+b[y];
for (int j=a[x];j>=a[y];j--)
{
dp[cur][j]|=dp[cur^1][j-a[y]];
}
for (int j=a[x];j>=b[y];j--)
{
dp[cur][j]|=dp[cur^1][j-b[y]];
}
}
for (int j=a[x];j>=0;j--)
{
if (dp[cur][j])
{
b[x]=sum-j;
return true;
}
}
return false;
}
int main()
{
n=read();
for (int i=2;i<=n;i++)
{
X=read();add(X,i);add(i,X);d[i]++;d[X]++;
}
if (n==1) //特判
{
printf("POSSIBLE\n");
return 0;
}
for (int i=1;i<=n;i++) a[i]=read();
if (dfs(1,0))
printf("POSSIBLE"); else printf("IMPOSSIBLE");
return 0;
}

CF739 B. Alyona and a tree

Alyona has a tree with $n$ vertices. The root of the tree is the vertex $1$. In each vertex Alyona wrote an positive integer, in the vertex i she wrote $a_i$. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).

Let’s define $dist(v,u)$ as the sum of the integers written on the edges of the simple path from $v$ to $u$.

The vertex $v$ controls the vertex $u$ $(v ≠ u)$ if and only if u is in the subtree of $v$ and $dist(v,u) ≤ a_u$.

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex $v$ what is the number of vertices $u$ such that $v$ controls $u$.

Input

The first line contains single integer $n$ ($1 ≤ n ≤ 2*10^5$).

The second line contains $n$ integers $a_1$, $a*_2$, …, $a_n$ ($1 ≤ a_i ≤ 10^9$) — the integers written in the vertices.

The next ($n - 1​$) lines contain two integers each. The $i​$-th of these lines contains integers $p_i​$ and $w_i​$ ($1 ≤ p_i≤ n​$, $1 ≤w_i ≤ 10^9​$) — the parent of the ($i + 1​$)-th vertex in the tree and the number written on the edge between $p_i​$ and ($i + 1​$).

It is guaranteed that the given graph is a tree.

Output

Print $n$ integers — the $i$-th of these numbers should be equal to the number of vertices that the $i$-th vertex controls.

Examples

Input1

1
2
3
4
5
6
5
2 5 1 4 6
1 7
1 1
3 5
3 6

Output1

1
1 0 1 0 0

Input2

1
2
3
4
5
6
5
9 7 8 6 5
1 1
2 1
3 1
4 1

Output2

1
4 3 2 1 0

Note

In the example test case the vertex 1 controls the vertex 3, the vertex 3 controls the vertex 5 (note that is doesn’t mean the vertex 1 controls the vertex 5).

题解

题意:一棵根节点为 $1$ 的树,每个点都有点值 $a_i$,每条边也有权值,$dist(v, u)$ 表示从 $v$ 到 $u$ 边权和,当 $u$ 时 $v$ 的子树并且 $dist(v, u) \le a_u$ 时$u$ 就受 $v$ 控制,输出每个结点能控制的结点数。

首先,考虑每个点受到多少个点的影响,然后发现,点u并不是很好把贡献转移到父节点。于是就想每个点能影响到前面的多少个点,然后用vector记一下前缀和,然后lower_bound一下,看下能影响到哪个位置,树上差分一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=2e5+10;
int n,Y;
ll a[maxn];
int fa[maxn],bj[maxn];
int to[maxn<<1],ne[maxn<<1];
ll w[maxn<<1];
int po[maxn],id;
vector<ll> A;
vector<ll> B;//id
inline void add(int x,int y,ll z)
{
to[++id]=y;w[id]=z;ne[id]=po[x];po[x]=id;
}
void dfs(int x,ll b)//b:前缀和
{
A.push_back(b);
B.push_back(x);//记录编号的
ll y;
if (x!=1)
{
y=b-a[x];
if (y<=0)//特判断,可以影响到上面所有的点
{
bj[fa[x]]++;
} else
{
if (lower_bound(A.begin(),A.end(),y)!=A.end())//对前面的点有影响
{
int p1=lower_bound(A.begin(),A.end(),y)-A.begin();
bj[fa[x]]++;
bj[B[p1-1]]--;
}
}
}
for (int i=po[x];i;i=ne[i])
{
if (to[i]==fa[x]) continue;
y=to[i];
dfs(y,b+w[i]);//往下扫
}
A.pop_back();//回溯???
B.pop_back();
}
void dfs1(int x)//再扫一遍统一下
{
for (int i=po[x];i;i=ne[i])
{
if (to[i]==fa[x]) continue;
dfs1(to[i]);
bj[x]+=bj[to[i]];
}
}
int main()
{
n=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=2;i<=n;i++)
{
fa[i]=read();Y=read();
add(i,fa[i],Y);add(fa[i],i,Y);
}
dfs(1,0);
dfs1(1);
for (int i=1;i<=n;i++) printf("%d ",bj[i]);
return 0;
}

855C. Helga Hufflepuff’s Cup

Harry, Ron and Hermione have figured out that Helga Hufflepuff’s cup is a horcrux. Through her encounter with Bellatrix Lestrange, Hermione came to know that the cup is present in Bellatrix’s family vault in Gringott’s Wizarding Bank.

The Wizarding bank is in the form of a tree with total n vaults where each vault has some type, denoted by a number between 1 to m. A tree is an undirected connected graph with no cycles.

The vaults with the highest security are of type k, and all vaults of type k have the highest security.

There can be at most x vaults of highest security.

Also, if a vault is of the highest security, its adjacent vaults are guaranteed to not be of the highest security and their type is guaranteed to be less than k.

Harry wants to consider every possibility so that he can easily find the best path to reach Bellatrix’s vault. So, you have to tell him, given the tree structure of Gringotts, the number of possible ways of giving each vault a type such that the above conditions hold.

Input

The first line of input contains two space separated integers, n and m — the number of vaults and the number of different vault types possible. (1 ≤ n ≤ 105, 1 ≤ m ≤ 109).

Each of the next n - 1 lines contain two space separated integers u**i and v**i (1 ≤ u**i, v**i ≤ n) representing the i-th edge, which shows there is a path between the two vaults u**i and v**i. It is guaranteed that the given graph is a tree.

The last line of input contains two integers k and x (1 ≤ k ≤ m, 1 ≤ x ≤ 10), the type of the highest security vault and the maximum possible number of vaults of highest security.

Output

Output a single integer, the number of ways of giving each vault a type following the conditions modulo 109 + 7.

Examples

Input

1
2
3
4
5
4 2
1 2
2 3
1 4
1 2

Output

1
1

Input

1
2
3
4
3 3
1 2
1 3
2 1

Output

1
13

Input

1
2
3
4
3 1
1 2
1 3
1 1

Output

1
0

Note

In test case 1, we cannot have any vault of the highest security as its type is 1 implying that its adjacent vaults would have to have a vault type less than 1, which is not allowed. Thus, there is only one possible combination, in which all the vaults have type 2.

题解

题意:

给你 $n$个点,$n-1$ 条边,让后给你个 $m$ ,再给你 $k$ 和 $x$ ,然后每个点可以是颜色 $1$~$k$ 有一个特殊颜色 $k$ 这个颜色最多出现 $x$次,然后和 $k$ 相邻的点颜色数值必须 $<k$ 求方案数

设 $dp_{i,j,k}$表示点 $i$ 颜色为 $j$ 整个子树 $i$ 有 $k$ 个点为特殊颜色的方案数

颜色范围这么大,显然不行,但是观察很容易发现,只有三种颜色:$k$ ,然后我们分别将他们设为0,1,2

然后就可以推出转移方程,时间复杂度:$O(nk^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=1e5+10;
const long long mod=1e9+7;
long long n,m,X,Y,k,s;
int to[maxn<<1];
int ne[maxn<<1];
int po[maxn],id;
long long dp[maxn][3][11],ans;//0:<k 1:=k 2:>k
long long f[2][3][11];
int du[maxn];
inline void add(int x,int y)
{
id++;to[id]=y;ne[id]=po[x];po[x]=id;
}
void Mod(long long &aa)
{
if (aa>=mod) aa-=mod;
}
void dfs(int x,int fa)
{
dp[x][0][0]=k-1;
dp[x][1][1]=1;
dp[x][2][0]=m-k;
if (du[x]==1&&x!=1) return;
for (int i=po[x];i;i=ne[i])
{
if (to[i]==fa) continue;
dfs(to[i],x);
}
int y;
memset(f,0,sizeof(f));
int cur=0;
f[0][0][0]=1;
f[0][1][0]=1;
f[0][2][0]=1;
for (int i=po[x];i;i=ne[i])
{
if (to[i]==fa) continue;
cur^=1;
memset(f[cur],0,sizeof(f[cur]));
y=to[i];
for (int w=0;w<=s;w++)//枚y子树的特殊颜色的个数
for (int j=s;j>=w;j--)
{
f[cur][0][j]+=f[cur^1][0][j-w]*(dp[y][0][w]+dp[y][1][w]+dp[y][2][w])%mod;
f[cur][1][j]+=f[cur^1][1][j-w]*(dp[y][0][w])%mod;
f[cur][2][j]+=f[cur^1][2][j-w]*(dp[y][0][w]+dp[y][2][w])%mod;
Mod(f[cur][0][j]);
Mod(f[cur][1][j]);
Mod(f[cur][2][j]);
}
}
for (int i=0;i<=s;i++)
{
dp[x][0][i]=(long long)(k-1)*f[cur][0][i]%mod;
if (i!=0) dp[x][1][i]=f[cur][1][i-1];
dp[x][2][i]=(long long)(m-k)*f[cur][2][i]%mod;
}
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
n=read();m=read();
for (int i=1;i<n;i++)
{
X=read();Y=read();
du[X]++;du[Y]++;
add(X,Y);add(Y,X);
}
k=read();s=read();
dfs(1,0);
for (int i=0;i<=s;i++)
{
ans+=dp[1][0][i];
Mod(ans);
ans+=dp[1][1][i];
Mod(ans);
ans+=dp[1][2][i];
Mod(ans);
}//统计答案
ans%=mod;
printf("%I64d\n",ans);
return 0;
}