[CF191](Fools and Roads)
solution: 나무 에 차이 점 이 있 습 니 다.
나무 에 차이 점 이 있 는 판 자 는 다음 과 같 습 니 다. 차이 점 그룹 p, 경로 s - > t, p [s] +, p [t] +, p [lca (s, t)] -, p [fa [lca [(s, t)]] -;
그리고 한 점 의 하위 트 리 내 차이 점 의 합 은 이 점 을 덮어 쓰 는 횟수 입 니 다. 그러나 이 문 제 는 우리 에 게 변 을 처리 하 라 고 요구 합 니 다.
그러면 저희 가 두 가지 방법 이 있어 요.
하 나 는 한 변 에 대해 새로운 점 은 이 변 을 대표 하고 이 점 에서 변 으로 향 하 는 두 점 의 연결 변 이다.
폭력 적 이지 만 머리 가 없다.
다른 하 나 는 한 변 의 두 점 중 깊이 가 비교적 큰 점 으로 이 변 을 대표 하 는 것 이다.
그러나 이때 원래 의 차분 조작 은 냄비 에서 나온다. p [s] +, p [t] +, p [lca (s, t)] - 2 (스스로 이해) 로 바 꿔 야 한다.
코드 붙 이기 (첫 번 째 방법, 오로라 서 ST 표 LCA 구하 기)
#include
#include
#include
#include
#include
#define N 400050
using namespace std;
vector G[N];
int n,m;
int dfn[N],pos[N],lg[N],dep[N];
int id[N],ans[N];
int st[35][N],cnt=0,plu[N],fa[N];
void aux(int x,int ff) {
dfn[++cnt]=x,pos[x]=cnt,fa[x]=ff;
for(int i=0; i>1]+1;
for(int i=1; i<=cnt; i++)st[0][i]=dfn[i];
for(int i=1; i<=lg[cnt]; i++)
for(int r=1; r+(1<y)swap(x,y);
int p=lg[y-x+1];
return mn(st[p][x],st[p][y-(1< 다음으로 전송:https://www.cnblogs.com/stepsys/p/10802586.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
