داوود و مشتلی برای تعطیلات به سواحل هاوایی رفتند و در طی عملیاتی مشتلی به داوود چندین…
- User
داوود و مشتلی برای تعطیلات به سواحل هاوایی رفتند و در طی عملیاتی مشتلی به داوود چندین هکتار از زمینهای هاوایی را بدهکار شد. نقشه سواحل هاوایی به شکل یک درخت هست ولی هنوز دانشمندان اطلاعات دقیقی از شکلش به دست نیاوردهاند. حالا مشتلی میخواهد از دست داوود فرار کند. از اونجا که این پولها برای داوود عددی حساب نمیشود، فقط در صورتی از مشتلی پولها را طلب میکند که فاصلهاش از مشتلی کمتر از d d باشد. مشتلی که طلای المپیاد حسابداری دارد، به حساب و کتاب روی میآورد. مشتلی ارزش یک درخت را برابر تعداد راسهایی از درخت مثل v v تعریف میکند که اگر داوود در راس v v باشد ، مشتلی بتواند در راسی قرار بگیرد که فاصلهاش از داوود بیشتر یا مساوی از d d باشد.
شایان از زمینشناسان معروف قرن 21 21 است و در مورد سواحل هاوایی تحقیق میکند. او درختی n n راسی و ریشهدار که طبق معمول ریشهاش راس 1 1 است را به مشتلی میدهد و میگوید نقشه سواحل هاوایی یکی از زیردرختهای این درخت است. حال مشتلی، درخت شایان و عدد d d را به شما ورودی میدهد و در قبال آن میخواهد به ازای هر راس مثل v v، ارزش زیردرخت v v را به دست آورید.
در یک درخت ریشهدار، زیردرخت راس v v شامل تمام رئوس مانند u u است که در کوتاهترین مسیر بین ریشه و u u راس v v ظاهر شده باشد.
ورودی در خط اول دو عدد n n و d d آمده است.
در خط بعدی n − 1 n−1 عدد است که در جایگاه i i ام پدر راس i + 1 i+1 ام آمده است.
2 ≤ n ≤ 3 × 1 0 5 2≤n≤3×10 5
1 ≤ d ≤ n 1≤d≤n
خروجی در یک خط n n عدد چاپ کنید که عدد i i ام ارزش زیردرخت راس i i است.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۷ n ≤ 300 n≤300 ۲ ۱۲ n ≤ 3000 n≤3000 ۳ ۱۷ ارتفاع درخت حداکثر ۴۰ است ۴ ۴۳ n ≤ 1 0 5 n≤10 5
۵ ۲۱ بدون محدودیت اضافی مثال ورودی نمونه ۱ 3 2 1 2 Plain text خروجی نمونه ۱ 2 0 0 Plain text ورودی نمونه ۲ 11 4 1 1 2 2 3 4 5 8 8 10 Plain text خروجی نمونه ۲ 11 7 0 0 0 0 0 0 0 0 0 Plain text ورودی نمونه ۳ 11 3 1 1 2 2 3 4 5 8 8 10 Plain text خروجی نمونه ۳ 11 8 0 0 3 0 0 2 0 0 0 java
- Assistant
To solve this problem, we'll calculate the eccentricity (maximum distance to any node in the tree) for each node. Once we have the eccentricities, for each node
v, we can count how many nodes in its subtree have eccentricity greater than or equal tod. This count will be the required value for nodev.Here's how we can approach this:
-
Compute the Eccentricities:
- Find one end of the diameter: Start with any node (say, node
1) and perform BFS to find the farthest node from1. Let's call this nodeu. - Find the other end of the diameter: Perform BFS starting from node
ufound in the previous step, to find the farthest node fromu. This node isv. Now the path betweenuandvis one of the longest paths in the tree (the diameter). - Calculate distances from
uandv:- Perform BFS from node
uto find distances fromuto every other node. - Perform BFS from node
vto find distances fromvto every other node.
- Perform BFS from node
- Compute eccentricities: For every node
x, the eccentricitye[x]is the maximum of the distances fromxtouandxtov.
- Find one end of the diameter: Start with any node (say, node
-
Compute the Counts for Each Subtree:
- Create a tree using the parent information and build adjacency lists.
- For each node
v, we'll perform a post-order traversal (DFS):- Initialize
cnt[v] = 1ife[v] ≥ delse0. - For each child
cofv, addcnt[c]tocnt[v]. - So,
cnt[v]will be the total number of nodes in the subtree rooted atvthat have eccentricity greater than or equal tod.
- Initialize
-
Print the Counts:
- After performing the traversal,
cnt[v]for each nodevis the required value to output.
- After performing the traversal,
This method works efficiently within the given constraints. It avoids computing all pair-wise distances and relies only on BFS and DFS traversals, which are
O(n)operations.Here's the complete code implementing this solution in Java:
import java.io.*; import java.util.*; public class Main { static List<Integer>[] adj; static int[] eccentricity; static int[] count; static int n, d; public static void main(String[] args) throws IOException { // Fast IO operations BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] tokens = br.readLine().split(" "); n = Integer.parseInt(tokens[0]); d = Integer.parseInt(tokens[1]); adj = new List[n + 1]; for(int i = 1; i <= n; i++) { adj[i] = new ArrayList<>(); } tokens = br.readLine().split(" "); for(int i = 2; i <= n; i++) { int parent = Integer.parseInt(tokens[i - 2]); adj[parent].add(i); adj[i].add(parent); } // Find first end of diameter int u = bfs(1)[0]; // Find other end of diameter int v = bfs(u)[0]; // Distances from u int[] distU = bfsDistances(u); // Distances from v int[] distV = bfsDistances(v); // Eccentricities eccentricity = new int[n + 1]; for(int i = 1; i <= n; i++) { eccentricity[i] = Math.max(distU[i], distV[i]); } // Build tree (since the tree is rooted, we can reconstruct the parent-child relationships) List<Integer>[] tree = new ArrayList[n + 1]; for(int i = 1; i <= n; i++) { tree[i] = new ArrayList<>(); } tokens = tokens = br.readLine().split(" "); int[] parent = new int[n + 1]; parent[1] = 0; for(int i = 2; i <= n; i++) { int p = Integer.parseInt(tokens[i - 2]); parent[i] = p; tree[p].add(i); } // Counts of nodes with eccentricity >= d in each subtree count = new int[n + 1]; dfs(1, tree); StringBuilder sb = new StringBuilder(); for(int i = 1; i <= n; i++) { sb.append(count[i]).append(' '); } System.out.println(sb.toString().trim()); } static int[] bfs(int start) { int[] dist = new int[n + 1]; Arrays.fill(dist, -1); Queue<Integer> queue = new LinkedList<>(); dist[start] = 0; queue.offer(start); int furthestNode = start; while(!queue.isEmpty()) { int u = queue.poll(); for(int v : adj[u]) { if(dist[v] == -1) { dist[v] = dist[u] + 1; queue.offer(v); if(dist[v] > dist[furthestNode]) { furthestNode = v; } } } } return new int[]{furthestNode, dist[furthestNode]}; } static int[] bfsDistances(int start) { int[] dist = new int[n + 1]; Arrays.fill(dist, -1); Queue<Integer> queue = new LinkedList<>(); dist[start] = 0; queue.offer(start); while(!queue.isEmpty()) { int u = queue.poll(); for(int v : adj[u]) { if(dist[v] == -1) { dist[v] = dist[u] + 1; queue.offer(v); } } } return dist; } static void dfs(int u, List<Integer>[] tree) { count[u] = 0; if(eccentricity[u] >= d) { count[u] = 1; } for(int v : tree[u]) { dfs(v, tree); count[u] += count[v]; } } } -
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.