Блог пользователя Gagandeep98

Автор Gagandeep98, история, 4 года назад, По-английски

I am stuck on Counting Path 1136 problem, and unable to think how to write an approach optimal to given constraints. Any hint or help is highly appreciated.

I cannot find any place where there is any hint for CSES problems(Except DP and Range Queries), hence thought this as the only possible option.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

Seems like a classic LCA + Segment tree problem.

Flatten the tree using dfs and update on the range by 1 from index of a to index of b for every path. (Update the subtree of LCA(a,b) by 1 and the subtrees of node a and node b by -1 (dont forget to update extra 1 for node a and node b specifically)).

There are edge cases, make sure you handle them.

Print all the segment tree values for all nodes in the end.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Thank you! But why is segment tree needed? I think LCA + array for range is sufficient.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please clarify one thing? Suppose I had a tree as shown below :

    EXAMPLE TREE

    Now let us assume that for the current path a=7 and b =5. So according to your algorithm, we will first find the of lca of a and b so here lca(a,b)=1 and then we'll add 1 to the subtree of node 1 and then add -1 to subtree of node 5 and node 7 (in this way we took care of nodes 10,11,12 and 9 that no update is made on them) but what about nodes 4,8 and 6 shouldn't we subtract 1 from them too? Sorry if I asked something very obvious or interpreted your algorithm incorrectly.
    EDIT: Got an AC by using (kind of)prefix sum approach using lca on the tree

    CODE FOR REFERENCE
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    ViciousCoder can you please clear a bit more..

    i was thinking of doing +1 on a range of tin[lca] to tout[lca] and -1 on tin[a] to tout[a] and tin[b] to tout[b]

    but clearly this is not covering all cases..

    can you please specify the segments you would carry out the operation on?

    (i understood what needs to be done without seg trees but i am looking for a soln with seg tree)

    mycode without seg tree: https://ideone.com/1NJn9n

  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you share code for this logic ?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

There are complicated data structure solutions to this problem. But this one can actually be solved by doing prefix sums on difference array on tree.

Break down each path into two vertical paths. Now, for each vertical path, in some vertex indexed array, do +1 for deeper point of vertical path and -1 for higher point.

After this, just do subteee sum of values in the vertex indexed array. It will represent paths going out of a vertex, which is what you wanted.

78837236 Accepted solution for an almost same problem on Codeforces

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ViciousCoder can you please share your solution using segment trees?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

//Here is my solution using difference array & LCA.

Your code here...
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long int
    //==============pbds==================== //
    // #include <ext/pb_ds/assoc_container.hpp>
    // #include <ext/pb_ds/tree_policy.hpp>
    // using namespace __gnu_pbds;
    
    // typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //set

    // typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset; //multiset<key,index>

    //==============debug=================== // 
    void _print(int t) {cerr << t;}
    void _print(string t) {cerr << t;}
    void _print(char t) {cerr << t;}
    void _print(long double t) {cerr << t;}
    void _print(double t) {cerr << t;}
    void _print(unsigned long long t) {cerr << t;}
    template <class T, class V> void _print(pair <T, V> p);
    template <class T> void _print(vector <T> v);
    template <class T> void _print(set <T> v);
    template <class T, class V> void _print(map <T, V> v);
    template <class T> void _print(multiset <T> v);
    template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
    template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
    template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
    template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
    template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
    #ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
    #else
    #define debug(x)
    #endif
    // ============= Solution =============== //
    int dp[200001][18]  ; 
    int level[200001] ; 
    int scanline[200001] ; 
    int ans[200001] ; 
    void computethesize(int node, int par, vector<vector<int>>&adj) {
        int sum=scanline[node] ; 
        for(auto child:adj[node]) {
            if(child!=par) {
                computethesize(child, node, adj) ; 
                sum+=ans[child]  ; 
            }
        }
        ans[node]=sum; 
    }
    void computethelevel(int node, int par, vector<vector<int>>&adj) {
        if(par!=-1) level[node]=1+level[par] ;
        for(auto child:adj[node]) {
            if(child!=par) computethelevel(child, node, adj)    ;
        } 
    }
    void dfs(int node, int par, vector<vector<int>>&adj) {
        dp[node][0]=par;
        for(int i=1; i<18; i++) {
            dp[node][i]=dp[dp[node][i-1]][i-1] ; 
        }
        for(auto child:adj[node]) {
            if(child!=par) dfs(child, node, adj) ; 
        } 
    }
    int lift(int node, int k) {
        for(int i=0; i<18; i++){
            if((1<<i)&k) node=dp[node][i] ; 
        }
        return node; 
    }
    int lca(int u, int v, vector<vector<int>>&adj) {
        if(level[u]!=level[v]) ; 
        int k=abs(level[u]-level[v]) ; 
        if(level[u]>level[v]) {
            u=lift(u, k) ; 
        }
        else if(level[v]>level[u]) {
            v=lift(v, k) ; 
        }
        if(u==v) return v; 
        for(int i=17; i>=0; i--) {
           int nu=dp[u][i] ; 
           int nv=dp[v][i] ;
            if(nu!=nv) {
                u=nu; 
                v=nv; 
            }
        }
        return dp[u][0] ;
    }
    void solve(){
         int n ,m; 
         cin>>n>>m; 
         vector<vector<int>>adj(n+1) ; 
         for(int i=1; i<n; i++) {
                 int u, v; 
                 cin>>u>>v; 
                 adj[u].push_back(v) ; 
                 adj[v].push_back(u) ; 
         }
         dfs(1,-1,adj) ;   
         computethelevel(1, -1, adj) ; 
         for(int i=1; i<=m; i++ ) {
            int u, v; 
            cin>>u>>v; 
            int l=lca(u, v ,adj) ; 
            scanline[l]--; 
            if(dp[l][0]!=-1) scanline[dp[l][0]]--; 
            scanline[u]++; 
            scanline[v]++; 
         }
         computethesize(1, -1, adj) ; 
         for(int i=1; i<=n; i++) cout<<ans[i]<<" "; 
     } 
    signed main()
    {
        ios_base::sync_with_stdio(false);   cin.tie(NULL);
        int test_case=1 ; 
         //     cin>>test_case; 
        while(test_case--) {
            solve(); 
        }
      return 0;
    }
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

simple dfs + LCA is enough for this problem. dont need any DS.
code

»
6 недель назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

One sol is the following:
maintain a counter on each node.
If a path is given as (a , b), modify the counters as
counter[a]++ , counter[b]++ , counter[lca(a , b)]-- , counter[parent(lca(a , b))]--.
The answer is the sum of counters of a subtree.