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

خانواده بلک یکی از اصیل ترین خانواده‌ها میان خانواده‌های جادوگری است و همه اعضای آن به…

  1. User

    خانواده بلک یکی از اصیل ترین خانواده‌ها میان خانواده‌های جادوگری است و همه اعضای آن به شجره‌نامه خانواده خود بسیار اهمیت می‌دهند. شجره‌نامه این خانواده به شکل یک درخت است و ریشه آن بزرگترین فرد خانواده بلک است. در این خانواده سنت‌های زیادی وجود دارد. مثلن گاهی یکی از اعضای خانواده تصمیم میگیرد جایزه‌ای برای بچه‌هایش بگیرد. نحوه جایزه دادن به این صورت است که فرد جایزه‌دهنده در آن روز جایزه را پیش خودش نگه‌میدارد و فردایش آن جایزه را به یکی از فرزندانش (در صورت وجود) می‌دهد. در صورتی که آن شخص، فرزندی نداشته باشد جایزه پیش خودش می‌ماند. وگرنه فرزندش همین کار را تکرار می‌کند. یعنی جایزه را یک روز پیش خود نگه می‌دارد و فردایش آن را به یکی از فرزندانش می‌دهد. این کار آنقدر تکرار می‌شود تا جایزه به یکی از بلک‌های جوان برسد. (منظور عضوی از خانوادهاست که هنوز فرزندی ندارد یعنی یکی از برگ‌های درخت شجره‌نامه)

    با گرفتن زمان جایزه فرستادن‌ها و شخص‌فرستنده جایزه به سوالاتی شبیه سوال زیر پاسخ دهید:

    یک عضو جوان خانواده بلک تا یک روز مشخص حداکثر چند جایزه گرفته است؟ ورودی در خط اول ورودی دو عدد n و q آمده اند که n تعداد اعضای خانواده بلک و q تعداد استفسارات (queryها) را نشان می‌دهد. در خط بعد n-1 عدد p 2 . . . p n p 2 ​ ...p n ​ آمده است که شجره نامه خانواده بلک را مشخص می‌کند. فرض کنید اعضای خانواده به ترتیب سن با اعداد 1 تا n شماره‌گذاری شده‌اند. عدد p i p i ​ شماره پدر(یا مادر) عضو شماره i را نشان‌ می‌دهد. رأس شماره 1 اولین عضو خانواده بلک است.

    در هر یک از q خط بعد در هر خط یک استفسار آمده است. در اول هر خط یک کاراکتر آمده است که نوع استفسار را مشخص می‌کند. کاراکتر $ نشان دهنده‌ جایزه دادن و ? نشان دهنده پرسش است.

    در حالت $، در ادامه دو عدد v و t آمده است که نشان می‌دهد عضو شماره vام خانواده در روز t تصمیم می‌گیرد جایزه بخرد! دقت کنید که یک نفر ممکن است جوان باشد و برای خودش جایزه بگیرد.

    در حالت ?، در ادامه دو عدد v و t آمده است که نشان می‌دهد عضو شماره vآم خانواده از ابتدا تا روز t (شامل خود این روز) حداکثر چند جایزه گرفته است؟ تضمین می‌شود که این عضو یک بلک جوان است(فرزندی ندارد).

    استفسارات به ترتیب نانزولی برحسب زمان در ورودی ظاهر شده‌اند.

    2 ≤ n ≤ 200

    000 2≤n≤200 000 1 ≤ p i ≤ i − 1 , 2 ≤ i ≤ n 1≤p i ​ ≤i−1,2≤i≤n

    1 ≤ q ≤ 200

    000 1≤q≤200 000

    1 ≤ v ≤ n 1≤v≤n

    1 ≤ t ≤ 1 0 9 1≤t≤10 9

    خروجی در خروجی به ازای هر پرسش، جواب آن را در یک خط چاپ کنید.

    زیرمسئله‌ها زیرمسئله نمره محدودیت ۱ ۱۵ n , q ≤ 2

    000 n,q≤2 000 ۲ ۱۰ n , q ≤ 50

    000 n,q≤50 000 و هر خانواده حداکثر یک بچه دارد. (گراف شجره‌نامه یک مسیر است.) ۳ ۵۵ n , q ≤ 50

    000 n,q≤50 000 ۴ ۲۰ بدون محدودیت اضافی مثال ورودی نمونه 5 8 1 2 2 1 21?332 1 ? 3 3 1 4 $ 2 4 ? 3 4 ? 3 5 ? 3 6 ? 5 6 Plain text خروجی نمونه 1 1 2 3 1 c++

  2. Assistant

    To solve this problem efficiently, we'll utilize a combination of Heavy-Light Decomposition (HLD) and Binary Indexed Trees (BIT). Here's a step-by-step breakdown of the approach:

    1. Understanding the Problem

    • We have a family tree where each member can give awards on certain days.
    • An award propagates down the family tree, moving from parent to child each day until it reaches a leaf node (a member without children).
    • We need to answer queries about how many awards a specific leaf has received up to a certain day.

    2. Key Observations

    • Tree Structure: The family tree is represented as a rooted tree with node 1 as the root.
    • Leaf Nodes: Queries are only about leaf nodes.
    • Propagation Condition: For a leaf node l to receive an award from node v on day t, the award must propagate from v to l within t days.
    • Transformed Condition: By defining t_diff = t - depth(l), we can transform the condition to s' - depth(v') <= t_diff, where s' is the day the award was given.

    3. Solution Strategy

    • Heavy-Light Decomposition (HLD):

      • Break down the tree into chains for efficient path queries.
      • Assign each node a unique position in a linear array.
    • Binary Indexed Tree (BIT):

      • Use BIT to keep track of the number of awards received by nodes up to certain positions in the HLD.
    • Event Sorting:

      • Treat both award giveaways ($ operations) and queries (? operations) as events.
      • Sort all events based on t_diff in ascending order. For events with the same t_diff, process award giveaways before queries to ensure correct counts.
    • Processing Events:

      • Traverse the sorted events.
      • For each award giveaway, update the BIT at the corresponding node's position.
      • For each query, use HLD to sum the number of awards along the path from the queried leaf to the root.

    4. Implementation Details

    • Tree Representation: Use adjacency lists to represent the tree.
    • HLD Implementation: Assign head, position, and other necessary properties to each node.
    • BIT Operations: Implement standard BIT operations (update and query) to handle range sum queries.
    • Handling Queries: For each query, calculate the required t_diff and use HLD paths to determine the number of awards received.

    5. Example Walkthrough

    Consider the sample input:

    5 8
    1 2 2 1
    $ 2 1
    ? 3 3
    $ 1 4
    $ 2 4
    ? 3 4
    ? 3 5
    ? 3 6
    ? 5 6
    

    Following the strategy:

    • Identify the tree structure and leaf nodes.
    • Assign HLD positions.
    • Sort and process events based on t_diff.
    • Update BIT and answer queries accordingly.

    6. Final Answer

    Here's the complete C++ implementation based on the above strategy:

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    // BIT implementation (1-based)
    struct BIT {
        int n;
        vector<int> tree;
    
        BIT(int size) : n(size), tree(size + 1, 0) {}
    
        void update(int idx, int delta=1){
            while(idx <= n){
                tree[idx] += delta;
                idx += idx & -idx;
            }
        }
    
        int query(int idx) const{
            int res = 0;
            int i = idx;
            while(i >0){
                res += tree[i];
                i -= i & -i;
            }
            return res;
        }
    
        // Query sum from l to r inclusive
        int query(int l, int r) const{
            if(l > r) return 0;
            return query(r) - query(l-1);
        }
    };
    
    // HLD implementation
    struct HLD {
        int n;
        vector<vector<int>> adj;
        vector<int> parent;
        vector<int> depth;
        vector<int> heavy;
        vector<int> head;
        vector<int> pos;
        int cur_pos;
    
        HLD(int size) : n(size), adj(size +1, vector<int>()), parent(size +1, 0),
                       depth(size +1, 0), heavy(size +1, -1),
                       head(size +1, 0), pos(size +1, 0), cur_pos(1) {}
    
        void add_edge(int u, int v){
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    
        // DFS to compute sizes and heavy child
        int dfs(int v, int p_node){
            parent[v] = p_node;
            int size =1;
            int max_size = 0;
            for(auto &u: adj[v]){
                if(u != p_node){
                    depth[u] = depth[v] +1;
                    int sz = dfs(u, v);
                    size += sz;
                    if(sz > max_size){
                        max_size = sz;
                        heavy[v] = u;
                    }
                }
            }
            return size;
        }
    
        // Decompose the tree
        void decompose(int v, int h){
            head[v] = h;
            pos[v] = cur_pos++;
            if(heavy[v] != -1){
                decompose(heavy[v], h);
                for(auto &u: adj[v]){
                    if(u != parent[v] && u != heavy[v]){
                        decompose(u, u);
                    }
                }
            }
        }
    
        // Initialize HLD
        void build(int root=1){
            dfs(root, -1);
            decompose(root, root);
        }
    
        // Query the path from u to v (assuming v is ancestor of u)
        int query_path(int u, const BIT &bit) const{
            int res =0;
            while(head[u] != head[1]){
                res += bit.query(pos[head[u]], pos[u]);
                u = parent[head[u]];
            }
            res += bit.query(pos[1], pos[u]);
            return res;
        }
    };
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
    
        int n, q;
        cin >> n >> q;
    
        vector<int> p(n+1, 0);
        // Read p2 to pn
        for(int i=2;i<=n;i++) cin >> p[i];
        
        // Build tree
        HLD hld(n);
        for(int i=2;i<=n;i++) {
            hld.add_edge(p[i], i);
        }
    
        // Compute depth and HLD
        hld.build(1);
    
        // Identify leaves
        vector<bool> is_leaf(n+1, true);
        for(int i=2;i<=n;i++) is_leaf[p[i]] = false;
    
        // Read all events
        struct Query {
            int id;
            int l;
            ll t;
        };
        struct Update {
            ll t_diff;
            int v;
        };
        struct Event {
            ll t_diff;
            int type; // 0 for update, 1 for query
            int v; // for update: node v; for query: leaf l
            int qid; // for query
        };
        vector<Event> events;
        int query_count =0;
        vector<Query> queries;
        // To store answers
        vector<int> answer(q, 0);
        for(int i=0;i<q;i++){
            char c;
            cin >> c;
            if(c == '$'){
                int v;
                ll s;
                cin >> v >> s;
                ll t_diff = s - hld.depth[v];
                events.push_back(Event{t_diff, 0, v, -1});
            }
            else { // '?'
                int l;
                ll t;
                cin >> l >> t;
                // Assuming l is a leaf
                ll t_diff = t - hld.depth[l];
                events.push_back(Event{t_diff, 1, l, query_count});
                queries.push_back(Query{query_count, l, t});
                query_count++;
            }
        }
    
        // Sort events by t_diff ascendingly, type 'update' before 'query' for same t_diff
        sort(events.begin(), events.end(), [&](const Event &a, const Event &b) -> bool{
            if(a.t_diff != b.t_diff) return a.t_diff < b.t_diff;
            return a.type < b.type; // 0 ('update') before 1 ('query')
        });
    
        // Initialize BIT
        BIT bit(n);
    
        // Process events
        for(auto &e: events){
            if(e.type ==0){
                // Update: insert into BIT
                bit.update(hld.pos[e.v], 1);
            }
            else{
                // Query
                if(e.t_diff <0){
                    answer[e.qid] =0;
                }
                else{
                    // Perform path query from l to root
                    int l = e.v;
                    // Ensure l is a leaf
                    // Sum over path from l to root
                    // Using HLD
                    // Implemented as a separate function
                    // But here, we implement it inline
                    int res =0;
                    while(hld.head[l] != hld.head[1]){
                        res += bit.query(hld.pos[hld.head[l]], hld.pos[l]);
                        l = hld.parent[hld.head[l]];
                    }
                    res += bit.query(hld.pos[1], hld.pos[l]);
                    answer[e.qid] = res;
                }
            }
        }
    
        // Output answers in the order of input queries
        for(int i=0;i<query_count;i++) cout << answer[i] << "\n";
    }