Stuck On CSES Problem Counting Paths: Please Provide Any Hint

→ Обратите внимание

До соревнования
Codeforces Global Round 28
14:43:13
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 994 Solution Discussion

aryanc403

До начала 40:53:11

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3442
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	atcoder_official	162
2	maomao90	162
2	Um_nik	162
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Stuck On CSES Problem Counting Paths: Please Provide Any Hint

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

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.

Gagandeep98
5 лет назад
25

Комментарии (19)

Показать архивные | Написать комментарий?

ViciousCoder

5 лет назад, # |

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

→ Ответить

Gagandeep98

5 лет назад, # ^ |

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

→ Ответить

ViciousCoder

5 лет назад, # ^ |

Whatever you are comfortable with for range updates, works. I am much more comfortable with ST, hence mentioned that.

→ Ответить

Gagandeep98

5 лет назад, # ^ |

Right, thanks :)

→ Ответить

ViciousCoder

5 лет назад, # ^ |

No problem :)

→ Ответить

Lelouch.Lamperouge

5 лет назад, # ^ |

← Rev. 2 →

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<bits/stdc++.h>
using namespace std;
const int mxN =2e5+2 ;
typedef vector<int> vi;
#define pb push_back
#define For(i,n) for(int i=0;i<n;i++)
vi adj[mxN] ;
int anc[mxN][18],d[mxN],n,m,a[mxN],c[mxN];
void dfs2(int v,int p){
  anc[v][0]=p ;d[v]=d[p]+1 ;
  for(int i=1;i<18;i++)
    anc[v][i]=~anc[v][i-1]?anc[anc[v][i-1]][i-1]:-1 ;
  for(int x:adj[v])
    if(x^p)
      dfs2(x,v) ;
}
int lca(int u,int v){
  if(d[u]<d[v])
    swap(u,v) ;
  for(int i=17;~i;--i)
    if(d[u]-(1<<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) ;
  vector<int>k(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] << " " ;
}

→ Ответить

Shameek

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

xruto

3 месяца назад, # ^ |

using LCA is enough to solve problem. I can suggest 3 tags for the problem, LCA, Math, Scanline.

→ Ответить

manish_joshi

5 лет назад, # |

← Rev. 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

→ Ответить

Lelouch.Lamperouge

5 лет назад, # ^ |

Thanks a ton, it really helped a lot !!

→ Ответить

faraz16iqbal

3 года назад, # |

ViciousCoder can you please share your solution using segment trees?

→ Ответить

1802042

14 месяцев назад, # |

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

→ Ответить

krishnash1355

14 месяцев назад, # ^ |

Can anyone help me in my code?? CSES Code

→ Ответить

SriniV

10 месяцев назад, # |

← Rev. 3 →

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.

→ Ответить

aman1117

7 месяцев назад, # ^ |

can you please tell me why it works? if there are any prerequisites please tell me

→ Ответить

SriniV

6 месяцев назад, # ^ |

Split a path (a , b) into 2 parts: a -> lca(a , b) and lca(a , b) -> b.
You want to increment all nodes in these paths or at least simulate such a thing. Since directly incrementing each node is too slow, lets denote the answer for each node as the sum of its subtree.

Now, if we want to include the path a -> lca(a , b), we just increment the node a. But now, any ancestor of lca(a , b) also has a in its subtree but SHOULDNT be included in the path. Hence, we decrement parent(lca(a , b)) by one, so that node and all its ancestors dont include a. This idea is analogous to prefix sums.

Now lets do path b -> lca(a , b). If we increment b, all nodes above it will also be incremented. However, notice that we have already incremented lca(a , b) in the previous path, so we are over counting that. Hence we decrement lca(a , b) by one.

In total, the operation boils down to incrementing a and b by one. Now every node in the path a -> b has been increased by 1 except the lca ( which has been increased by 2 ). Furthermore, every ancestor of the lca has also been increased by 2. To counter this, we subtract one from the lca ( to make it 1 and all nodes above it 1 ), and one from the parent of the lca (to make it 0 and all nodes above it 0).

Not sure if that made any sense, but hope that helps :)

→ Ответить