HDU 4812 D Tree 树上点分治 求逆元

D Tree

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)

Problem Description

There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod 106 + 3) equals to K?
Can you help them in solving this problem?

Input

There are several test cases, please process till EOF.
Each test case starts with a line containing two integers N(1 <= N <= 105) and K(0 <=K < 106 + 3). The following line contains n numbers vi(1 <= vi < 106 + 3), where vi indicates the integer on vertex i. Then follows N - 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y.

Output

For each test case, print a single line containing two integers a and b (where a < b), representing the two endpoints of the chain. If multiply solutions exist, please print the lexicographically smallest one. In case no solution exists, print “No solution”(without quotes) instead.
For more information, please refer to the Sample Output below.

Sample Input

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

Sample Output

3 4
No solution

Hint

1. “please print the lexicographically smallest one.”是指: 先按照第一个数字的大小进行比较,若第一个数字大小相同,则按照第二个数字大小进行比较,依次类推。 2. 若出现栈溢出,推荐使用C++语言提交,并通过以下方式扩栈: #pragma comment(linker,"/STACK:102400000,102400000") 

Source
 

 

HDU 4871 Shortest-path tree 最短路生成树 树上点分治

Shortest-path tree

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 130712/130712 K (Java/Others)

Problem Description

Given a connected, undirected graph G, a shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.
We may construct a shortest-path tree using the following method:
We consider a shortest-path tree rooted at node 1. For every node i in the graph G, we choose a shortest path from root to i. If there are many shortest paths from root to i, we choose the one that the sequence of passing nodes' number is lexicographically minimum. All edges on the paths that we chose form a shortest-path tree.
Now we want to know how long are the longest simple paths which contain K nodes in the shortest-path tree and how many these paths? Two simple paths are different if the sets of nodes they go through are different.

Input

The first line has a number T (T <= 10), indicating the number of test cases.
For each test case, the first line contains three integers n, m, k(1<=n<=30000,1<=m<=60000,2<=k<=n), denote the number of nodes, the number of edges and the nodes of required paths.
Then next m lines, each lines contains three integers a, b, c(1<=a, b<=n, 1<=c<=10000),denote there is an edge between a, b and length is c.

Output

For each case, output two numbers, denote the length of required paths and the numbers of required paths.

Sample Input

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

Sample Output

3 4

Author

FZU

Source

 
 
 

 

Codeforces 746F Music in Car 二指针 multiset

http://codeforces.com/contest/746/problem/F

F. Music in Car

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Sasha reaches the work by car. It takes exactly k minutes. On his way he listens to music. All songs in his playlist go one by one, after listening to the i-th song Sasha gets a pleasure which equals ai. The i-th song lasts for ti minutes.

Before the beginning of his way Sasha turns on some song x and then he listens to the songs one by one: at first, the song x, then the song (x + 1), then the song number (x + 2), and so on. He listens to songs until he reaches the work or until he listens to the last song in his playlist.

Sasha can listen to each song to the end or partly.

In the second case he listens to the song for integer number of minutes, at least half of the song's length. Formally, if the length of the song equals d minutes, Sasha listens to it for no less than minutes, then he immediately switches it to the next song (if there is such). For example, if the length of the song which Sasha wants to partly listen to, equals 5 minutes, then he should listen to it for at least 3 minutes, if the length of the song equals 8 minutes, then he should listen to it for at least 4 minutes.

It takes no time to switch a song.

Sasha wants to listen partly no more than w songs. If the last listened song plays for less than half of its length, then Sasha doesn't get pleasure from it and that song is not included to the list of partly listened songs. It is not allowed to skip songs. A pleasure from a song does not depend on the listening mode, for the i-th song this value equals ai.

Help Sasha to choose such x and no more than w songs for partial listening to get the maximum pleasure. Write a program to find the maximum pleasure Sasha can get from the listening to the songs on his way to the work.

Input

The first line contains three integers n, w and k (1 ≤ w ≤ n ≤ 2·105, 1 ≤ k ≤ 2·109) — the number of songs in the playlist, the number of songs Sasha can listen to partly and time in minutes which Sasha needs to reach work.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 104), where ai equals the pleasure Sasha gets after listening to the i-th song.

The third line contains n positive integers t1, t2, ..., tn (2 ≤ ti ≤ 104), where ti equals the length of the i-th song in minutes.

Output

Print the maximum pleasure Sasha can get after listening to the songs on the way to work.

Examples

Input

Output

Input

Output

Input

Output

Input

Output

Note

In the first example Sasha needs to start listening from the song number 2. He should listen to it partly (for 4 minutes), then listen to the song number 3 to the end (for 3 minutes) and then partly listen to the song number 4 (for 3 minutes). After listening to these songs Sasha will get pleasure which equals 4 + 3 + 5 = 12. Sasha will not have time to listen to the song number 5 because he will spend 4 + 3 + 3 = 10 minutes listening to songs number 2, 3 and 4 and only 1 minute is left after that.

 

 

Codeforces 752F Santa Clauses and a Soccer Championship 树的重心 贪心

F. Santa Clauses and a Soccer Championship

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The country Treeland consists of n cities connected with n - 1 bidirectional roads in such a way that it's possible to reach every city starting from any other city using these roads. There will be a soccer championship next year, and all participants are Santa Clauses. There are exactly 2k teams from 2k different cities.

During the first stage all teams are divided into k pairs. Teams of each pair play two games against each other: one in the hometown of the first team, and the other in the hometown of the other team. Thus, each of the 2k cities holds exactly one soccer game. However, it's not decided yet how to divide teams into pairs.

It's also necessary to choose several cities to settle players in. Organizers tend to use as few cities as possible to settle the teams.

Nobody wants to travel too much during the championship, so if a team plays in cities u and v, it wants to live in one of the cities on the shortest path between u and v (maybe, in u or in v). There is another constraint also: the teams from one pair must live in the same city.

Summarizing, the organizers want to divide 2k teams into pairs and settle them in the minimum possible number of cities m in such a way that teams from each pair live in the same city which lies between their hometowns.

Input

The first line of input contains two integers n and k (2 ≤ n ≤ 2·105, 2 ≤ 2k ≤ n) — the number of cities in Treeland and the number of pairs of teams, respectively.

The following n - 1 lines describe roads in Treeland: each of these lines contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) which mean that there is a road between cities a and b. It's guaranteed that there is a path between any two cities.

The last line contains 2k distinct integers c1, c2, ..., c2k (1 ≤ ci ≤ n), where ci is the hometown of the i-th team. All these numbers are distinct.

Output

The first line of output must contain the only positive integer m which should be equal to the minimum possible number of cities the teams can be settled in.

The second line should contain m distinct numbers d1, d2, ..., dm (1 ≤ di ≤ n) denoting the indices of the cities where the teams should be settled.

The k lines should follow, the j-th of them should contain 3 integers uj, vj and xj, where uj and vj are the hometowns of the j-th pair's teams, and xj is the city they should live in during the tournament. Each of the numbers c1, c2, ..., c2k should occur in all uj's and vj's exactly once. Each of the numbers xj should belong to {d1, d2, ..., dm}.

If there are several possible answers, print any of them.

Example

Input

Output

Note

In the first test the orginizers can settle all the teams in the city number 2. The way to divide all teams into pairs is not important, since all requirements are satisfied anyway, because the city 2 lies on the shortest path between every two cities from {2, 4, 5, 6}.

 

 

Codeforces749E Inversions After Shuffle 逆序数的期望 树状数组

http://codeforces.com/problemset/problem/749/E

E. Inversions After Shuffle

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation of integers from 1 to n. Exactly once you apply the following operation to this permutation: pick a random segment and shuffle its elements. Formally:

  1. Pick a random segment (continuous subsequence) from l to r. All segments are equiprobable.
  2. Let k = r - l + 1, i.e. the length of the chosen segment. Pick a random permutation of integers from 1 to k, p1, p2, ..., pk. All k! permutation are equiprobable.
  3. This permutation is applied to elements of the chosen segment, i.e. permutation a1, a2, ..., al - 1, al, al + 1, ..., ar - 1, ar, ar + 1, ..., an is transformed to a1, a2, ..., al - 1, al - 1 + p1, al - 1 + p2, ..., al - 1 + pk - 1, al - 1 + pk, ar + 1, ..., an.

Inversion if a pair of elements (not necessary neighbouring) with the wrong relative order. In other words, the number of inversion is equal to the number of pairs (i, j) such that i < j and ai > aj. Find the expected number of inversions after we apply exactly one operation mentioned above.

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of the permutation.

The second line contains n distinct integers from 1 to n — elements of the permutation.

Output

Print one real value — the expected number of inversions. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 9.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Input

Output

 

 

POJ 1038 Bugs Integrated, Inc. 三进制状态压缩DP

Bugs Integrated, Inc.

Time Limit: 15000MS Memory Limit: 30000K
Case Time Limit: 5000MS

Description

Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.

Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.
Task
You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.

Input

The first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).

Output

For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.

Sample Input

Sample Output

Source

题意

如图,给定一个大小为N*M的矩阵,其中M<=10,矩阵中存在一些坏点,往矩阵中放入2*3或者3*2的小方块,坏点不能被小方块覆盖,问矩阵中最多能放入多少个小方块。

思路

由于M<=10,可以使用状态三进制压缩DP,用一个三进制的数表示每一行的状态,很显然,需要写一对函数来进行状态的编码和解码。对于每一个格子对应三进制的每一位:如果这一位是0,表示这个格子被占用;如果这一位是1,表示这个格子未被占用,但是他上方的格子被占用;如果这一位是2,表示这一个格子和他上方的一个格子都没被占用。当获取到上一排的一个有效状态的时候,通过dfs生成若干个这一排的有效状态,假设上一排的状态用last数组表示,这一排的状态用now数组表示,考虑这一排每一个位置pos小方块的放法:首先,如果这个格子是坏点,那么只能强行标记为已经占用的状态now[pos]=0,dfs后直接返回;如果考虑横着放,则需要now[pos-2]=2且now[pos-1]=2且last[pos]>=1,将now数组相关位置设置为0后再进行dfs,注意dfs返回后,要将now数组还原;如果考虑竖着放,则需要保证now[pos-1]=2且last[pos-1]=2且last[pos]=2,进行dfs也同样需要对now数组进行置位或还原;然后开可以考虑不放的情况,将now[pos]设置为min(2,last[pos]+1)即可。dfs的同时,还需要记录新添加的小方块的个数。当dfs到达边界的时候,进行dp的转移。
 

 

HDU 5721 Palace 求最近点对 + 对答案的贡献


Palace

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.
There are $ n $ palaces in the underworld, which can be located on a 2-Dimension plane with $ (x, y) $ coordinates (where $ x, y $ are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.
However, the underworld is mysterious and changes all the time. At different times, exactly one of the $ n $ palaces disappears.
Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.
Print the sum of the distance after every single palace has disappeared.
To avoid floating point error, define the distance $ d $ between palace $ (x_1, y_1) $ and $ (x_2, y_2) $ as $ d = (x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2 $.

Input

The first line of the input contains an integer $ T $ $ (1 \le T \le 5) $, which denotes the number of testcases.
For each testcase, the first line contains an integers $ n $ $ (3 \le n \le 10 ^ 5) $, which denotes the number of temples in this testcase.
The following $ n $ lines contains $ n $ pairs of integers, the $ i $-th pair $ (x, y) $ $ (-10 ^ 5 \le x,y \le 10 ^ 5) $ denotes the position of the $ i $-th palace.

Output

For each testcase, print an integer which denotes the sum of the distance after every single palace has disappeared.

Sample Input

1
3
0 0
1 1
2 2

Sample Output

12

Hint

If palace $ (0,0) $ disappears,$ d = (1-2) ^ 2 + (1 - 2) ^ 2 = 2 $; If palace $ (1,1) $ disappears,$ d = (0-2) ^ 2 + (0 - 2) ^ 2 = 8 $; If palace $ (2,2) $ disappears,$ d = (0-1) ^ 2 + (0-1) ^ 2 = 2 $; Thus the answer is $ 2 + 8 + 2 = 12 $。

Source

 

题意

给出n个点的坐标,假设第i个点消失后,最近点对的距离的平方为d,求d的和。

思路

会发现,这n个点的最近点对的距离对答案的贡献系数为(n-2),因为除了删除这两个最近点对,其它点的删除都不会影响最近点对的距离。后面分别删除这两个点,再求出最近点对的距离求和即可。求最近点对可以用KD-tree或者CDQ分治。
 
KD-tree

 

CDQ分治

 

 

 
 

HDU 5992 Finding Hotels KD-Tree求最近点


Finding Hotels

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)

Problem Description

There are N hotels all over the world. Each hotel has a location and a price. M guests want to find a hotel with an acceptable price and a minimum distance from their locations. The distances are measured in Euclidean metric.

Input

The first line is the number of test cases. For each test case, the first line contains two integers N (N ≤ 200000) and M (M ≤ 20000). Each of the following N lines describes a hotel with 3 integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N), in which x and y are the coordinates of the hotel, c is its price. It is guaranteed that each of the N hotels has distinct x, distinct y, and distinct c. Then each of the following M lines describes the query of a guest with 3 integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N), in which x and y are the coordinates of the guest, c is the maximum acceptable price of the guest.

Output

For each guests query, output the hotel that the price is acceptable and is nearest to the guests location. If there are multiple hotels with acceptable prices and minimum distances, output the first one.

Sample Input

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

Sample Output

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

Source

题意

先给出N(N ≤ 200000) 个宾馆的坐标和价格,再给出M (M ≤ 20000)次询问,每次询问给出客人所在的位置和能接受价格的上限,求离客人最近的且能价格能接受的宾馆的坐标和价格,如果有多个满足,输出id最小的。

思路

按照坐标建立KD树,并且维护树中价格的最小值,查询的时候,如果发现这个子树中的最小价格已经大于的能接受价格的上限,就可以不再继续查下去了。要注意的是,继续查询的条件需要从小于改成小于等于,因为还要求id最小。