Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

داوود و مشتلی برای تعطیلات به سواحل هاوایی رفتند و در طی عملیاتی مشتلی به داوود چندین…

  1. 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

  2. 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 to d. This count will be the required value for node v.

    Here's how we can approach this:

    1. Compute the Eccentricities:

      • Find one end of the diameter: Start with any node (say, node 1) and perform BFS to find the farthest node from 1. Let's call this node u.
      • Find the other end of the diameter: Perform BFS starting from node u found in the previous step, to find the farthest node from u. This node is v. Now the path between u and v is one of the longest paths in the tree (the diameter).
      • Calculate distances from u and v:
        • Perform BFS from node u to find distances from u to every other node.
        • Perform BFS from node v to find distances from v to every other node.
      • Compute eccentricities: For every node x, the eccentricity e[x] is the maximum of the distances from x to u and x to v.
    2. 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] = 1 if e[v] ≥ d else 0.
        • For each child c of v, add cnt[c] to cnt[v].
        • So, cnt[v] will be the total number of nodes in the subtree rooted at v that have eccentricity greater than or equal to d.
    3. Print the Counts:

      • After performing the traversal, cnt[v] for each node v is the required value to output.

    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];
            }
        }
    }
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.