변 분
나무의 분 치 는 점 과 비슷 하 다. 매번 에 양쪽 노드 의 수량 이 상대 적 으로 가 까 운 한 변 (중심 과 비슷 하 다) 을 찾 은 다음 에 이 변 을 통과 하 는 경 로 를 고려 한 다음 에 변 의 양쪽 을 각각 고려한다.국화 그림 에 대해 직접 변 분 하면 복잡 도 는 O (logn) 에서 O (n) 로 퇴화 될 것 이다. 따라서 변 분 하기 전에 rebuild: 각 노드 의 아들 노드 개 수 를 통계 해 야 한다. 만약 에 S (보통 2 이 고 실제 상황 에 따라 조정 할 수 있다) 보다 크 면 아들 노드 에서 S 개의 허 점 으로 바 꾸 고 그들 과 허 변 을 연결 해 야 한다.원래 의 아들 노드 는 평균 적 으로 S 개의 허 점 아래 에 분배 되 었 다. 원래 의 아들 노드 와 허 점 의 변 은 바로 그들 과 원래 의 아버지 노드 간 의 변 이 고 허 점 의 점 권 과 허 변 의 변 권 은 실제 상황 에 따라 조정 된다.점 에 비해 매번 원래 의 나 무 를 두 개 로 나 누고 점 수 는 여러 개 로 나 누 어 처리 하기 가 상대 적 으로 쉬 우 며 rebuild 를 해 야 한 다 는 단점 이 있어 상수 가 상대 적 으로 크다.
코드
#define P pair<int,int>
#define mp make_pair
#define fi first
#define se second
inline void rebuild()
{
memset(first,-1,sizeof(first)),bb=1;
int i,j,p,q;
for(i=1; i<=n; i++)
{
if(son[i].size()<=2)
{
for(j=0; jelse
{
p=++n,q=++n;
for(j=0; jif(j&1) son[p].push_back(son[i][j]),qn[p].push_back(qn[i][j]);
else son[q].push_back(son[i][j]),qn[q].push_back(qn[i][j]);
}
son[i].clear(),qn[i].clear();
son[i].push_back(p),son[i].push_back(q);
qn[i].push_back(0),qn[i].push_back(0);
ad(i,p,0),ad(i,q,0);
}
}
}
void gs(int now,int last)
{
int p,q;
size[now]=1;
for(p=first[now]; p!=-1; p=bn[p].next)
{
if(vis[p>>1] || bn[p].to==last) continue;
gs(bn[p].to,now);
size[now]+=size[bn[p].to];
}
}
P gr(int now,int last,int tot)
{
int p,q;
P res=mp(tot,0);
for(p=first[now]; p!=-1; p=bn[p].next)
{
if(vis[p>>1] || bn[p].to==last) continue;
res=min(res,gr(bn[p].to,now,tot));
res=min(res,mp((int)abs(tot-size[bn[p].to]*2),(int)(p>>1)));
}
return res;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
예제 1.15 UVALive-3902 트리의 검색컨베이어 도어 제목 대의: n대의 기계는 하나의 트리 네트워크로 연결되어 잎 노드는 클라이언트이고 다른 노드는 서버이다. 처음에는 한 대의 서버만 하나의 서비스를 제공했지만 k의 거리 내의 클라이언트만 덮어쓸 수 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
