Lazy_Propagation

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5916 🧐 관찰 및 접근 # 트리가 주어진다. 두 정점 사이 경로에 1을 더한다. 두 정점 사이 경로의 가중치의 합을 계산한다. 나이브하게는 $O(QN)$이겠지만, HLD와 Lazy 세그먼트 트리를 이용해서 $O(Qlog^2N)$정도에 계산할 수 있을 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; Tree tree(N); rep(i, 0, N-1){ int u, v; cin >> u >> v; tree.add_edge(u, v); } tree.build(); LazySegmentTree seg(N+1); while(M--){ char op; cin >> op; int u, v; cin >> u >> v; if(op == 'P'){ vector<pii> segs = tree.hld_path(u, v, false, false); for(auto [L, R]: segs) seg.update(L, R, 1); } else{ ll ans = 0; vector<pii> segs = tree.hld_path(u, v, false, false); for(auto [L, R]: segs) ans += seg.query(L, R); cout << ans << '\n'; } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31055 번역 문제 번역 # Bessie는 수학 지식을 향상시키기 위해 그래프 이론 강좌를 수강하고 있는데, 다음 문제에서 막혔습니다. 그녀를 도와주세요! 연결된 무방향 그래프가 주어집니다. 정점은 $1\dots N$으로, 간선은 $1\dots M$으로 라벨링되어 있습니다 ($2\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 10^5$). 그래프의 각 정점 $v$에 대해 다음 과정을 수행합니다: