### Gagandeep98's blog

By Gagandeep98, history, 3 years ago,

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

| Write comment?
 » 3 years ago, # | ← 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.
•  » » 3 years ago, # ^ |   +8 Thank you! But why is segment tree needed? I think LCA + array for range is sufficient.
•  » » » 3 years ago, # ^ |   +5 Whatever you are comfortable with for range updates, works. I am much more comfortable with ST, hence mentioned that.
•  » » » » 3 years ago, # ^ |   +3 Right, thanks :)
•  » » » » » 3 years ago, # ^ |   0 No problem :)
•  » » 3 years ago, # ^ | ← 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 #include using namespace std; const int mxN =2e5+2 ; typedef vector vi; #define pb push_back #define For(i,n) for(int i=0;i=d[v]) u=anc[u][i] ; if(u==v) return u ; for(int i =17;~i;--i){ if(anc[u][i]^anc[v][i]){ u=anc[u][i],v=anc[v][i] ; } } return anc[u][0] ; } int dfs3(int v,int p){ c[v]=a[v] ; for(int x:adj[v]) if(x^p) c[v]+=dfs3(x,v); return c[v] ; } signed main() { memset(a,0,sizeof(a)) ; cin >> n >> m ; For(i,n-1){ int u,v ; cin >> u >> v ; adj[v].pb(u) ;adj[u].pb(v) ; } dfs2(1,0) ; vectork(n+1); For(i,m){ int u,v,l;cin >> u >> v ; l = lca(u,v) ; k[l]++ ; ++a[u];++a[v];a[l]-=2 ; } dfs3(1,0) ; for(int i=1;i<=n;i++) cout << c[i]+k[i] << " " ; } 
•  » » » 3 weeks ago, # ^ |   0 Then what is your idea for the accepted code?
•  » » 3 years ago, # ^ | ← 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
•  » » 4 months ago, # ^ |   0 can you share code for this logic ?
 » 3 years ago, # | ← 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 years ago, # ^ |   0 Thanks a ton, it really helped a lot !!
 » 2 years ago, # |   0 ViciousCoder can you please share your solution using segment trees?
 » 2 months ago, # |   0 //Here is my solution using difference array & LCA. Your code here... #include using namespace std; #define int long long int //==============pbds==================== // // #include // #include // using namespace __gnu_pbds; // typedef tree, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //set // typedef tree, null_type,less >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset; //multiset //==============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 void _print(pair p); template void _print(vector v); template void _print(set v); template void _print(map v); template void _print(multiset v); template void _print(pair p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";} template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template void _print(map 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>&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>&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>&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<>&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>adj(n+1) ; for(int i=1; i>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<>test_case; while(test_case--) { solve(); } return 0; }