F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Black White Tree

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 175    Accepted Submission(s): 80


Problem Description
Alex has a tree $T$ with $n$ vertices conveniently labeled with $1,2,...,n$. Each vertex of the tree is colored black or white. For every integer pair $(a, b)$, Alex wants to know whether there is a subtree of $T$ with exact $a$ white vertices and $b$ black vertices.

A subtree of $T$ is a subgraph of $T$ that is also a tree.
 

Input
There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 100)$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ $(1 \le n \le 2000)$. The next line contains a binary string $s$ length $n$ where $s_i$ denoting the color of the $i$-th vertex ('0' means white, while '1' means black). Each of the following $n - 1$ lines contains two integers $a_i, b_i$, denoting an edge between vertices $a_i$ and $b_i$ $(1 \le a_i, b_i \le n)$.
 

Output
For each test case, output an integer $W = \sum_{a=0}^{n}\sum_{b=0}^{n}{(a+1)(b+1)S(a,b)}$. $S(a,b)=1$ if there is a subtree with exact $a$ white vertices and $b$ black vertices, or $0$ otherwise.
 

Sample Input
3 4 1010 1 4 2 4 3 4 3 101 1 2 2 3 10 1010111001 1 2 1 3 1 8 2 4 2 6 2 7 3 9 4 5 7 10
 

Sample Output
33 15 365
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 04:58:27, Gzip enabled