제 수준에 맞지 않는 문제를 하나 풀고 있습니다.

너무 어렵네요.  다른분들 코드와 에디토리얼을 봐도 도저히 이해가 되지 않아서 질문 올립니다.

문제는 바로 요녀석입니다.

http://codeforces.com/problemset/problem/372/D

 어떤 트리 T가 있고 , 임의의 버텍스 v가 있을때

v에서 트리 T까지의 최단거리를 아래코드와 같이 표현하고있더라고요

at변수->dfs의 방문순서

R=dfs방문시  v보다 방문순서가 빠른 노드(T에 포함되어 있는 버텍스중에)

L=dfs방문시 v보다 방문순서가 늦은 노드(T에 포함되어 있는 버텍스중에)

dep=root(1번노드) 노드로부터의 최단거리

v에서 트리 T까지의 최단거리 : dep[u] - dep[lca(u, L)] - dep[lca(u, R)] + dep[lca(L, R)];

저 식이 왜 성립하는지 잘 모르겠습니다.

고수님들 도와주십쇼 ㅠ

댓글을 작성하려면 로그인해야 합니다.