HBC210079BonVoyage题解

柳絮泡泡算法基础篇 2023-11-10 13:53:02 41 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

BonVoyageBon VoyageBonVoyage is a strong rowing team. As one of the three members, Apollo wants to help his teammates to solve tree problems faster. He plans to leave a tree problem to his teammates every day to train them. If his teammates failed to solve it, as a punishment, they would have to take turns to pay Apollo for a day's meal. Today is the first day for them to execute the plan. Facing Apollo's tough problem, his teammates decide to ask you for help. In return, they promise to give you half of the money that is saved for not having to pay Apollo's meal. Smart as you are, could you help them solve the following problem and get this huge sum ?

Bon VoyageBon VoyageBon Voyage is a strong rowing team. As one of the three members, Apollo wants to help his teammates to solve tree problems faster. He plans to leave a tree problem to his teammates every day to train them. If his teammates failed to solve it, as a punishment, they would have to take turns to pay Apollo for a day's meal. Today is the first day for them to execute the plan. Facing Apollo's tough problem, his teammates decide to ask you for help. In return, they promise to give you half of the money that is saved for not having to pay Apollo's meal. Smart as you are, could you help them solve the following problem and get this huge sum (Apollo eats a lot)? Given a tree with n nodes numbered from 1 to n. The node 1 is the root. Each node i has an associated value v[i]. Denote K as the distance coefficient, and W as the target value. Denote the depth of node i as dep[i]. The depth of node 1 (dep[1]) is 1. For each node, its lili valuelili valuelili value is defined as follows: For some array c, let's denote a lili sequence as a sequence of indices p1,p2,...,plp_1, p_2, ... , p_lp1,p2,...,pl such that 1≤p1pip_{i+1} > p_ipi+1>pi and c[pi+1]>c[pi]c[p_{i+1}] > c[p_i]c[pi+1]>c[pi]. If the simple path from u1u_1u1 to umu_mum consists of m nodes namely u1→u2→u3→...um−1→umu_1 to u_2 to u_3 to ... u_{m-1} to u_mu1→u2→u3→...um−1→um, then the lili valuelili valuelili value of path from u1u_1u1 to umu_mum is the length of {v[u1],v[u2],...,v[um]}left{v[u_1], v[u_2], ..., v[u_m]right}{v[u1],v[u2],...,v[um]}'s longest lili sequence. For nodes satisfying dep[i]≥Kdep[i]ge Kdep[i]≥K : Let u be the node on the path from node 1 (root) to node i, whose distance to node i is K (that is, the path beginning from u to i including both ends has a total of K nodes). The lili valuelili valuelili value of node i equals to the lili valuelili valuelili value of path from u to i. For nodes satisfying dep[i] < K: The lili valuelili valuelili value of node i equals to the lili valuelili valuelili value of path from 1 to i. Please calculate the number of nodes in the tree whose lili value≥Wlili value ge Wlili value≥W for all K from 1 to n.