1681 공공 조상
Description
거대 한 가족 이 있 습 니 다. 모두 n 명 입 니 다.이 n 명의 조상 관 계 는 마침 나무 모양 의 구 조 를 형성 한 것 으로 알려 져 있다.
또 다른 미 지 의 평행 우주 에서 이 n 명의 조상 관 계 는 아직도 나무 구조 이지 만 그들 은 서로 간 의 관 계 는 완전히 다르다. 원래 의 조상 은 후대 가 되 었 고 후손 은 또래 가 되 었 을 것 이다.
두 사람의 친밀 도 는 이 두 평행 우주 에서 얼마나 많은 사람들 이 그들의 공공 조상 이 었 는 지 정의 한다.
전체 가족의 친밀 도 는 임의의 두 사람의 친밀 도의 총화 로 정의 된다.
Input
첫 번 째 줄 의 개수 n (1 < = n < = 100000)
다음 n - 1 줄 마다 두 개의 수 x, y 는 첫 번 째 평행 우주 x 가 y 의 아버지 라 는 것 을 나타 낸다.
다음 n - 1 줄 마다 두 개의 수 x, y 는 두 번 째 평행 우주 x 가 y 의 아버지 라 는 것 을 나타 낸다.
Output
한 수 는 온 가족의 친밀 도 를 나타 낸다.
Input example
5 1 3 3 5 5 4 4 2 1 2 1 3 3 4 1 5
Output example
6
Solution
신기 한 데이터 구조 문제 입 니 다. 먼저, 우 리 는 dfs 에서 첫 번 째 나 무 를 겪 고 각 점 의 시간 스탬프 와 시간 스탬프 (이 점 은 tarjan 과 유사 합 니 다) 를 기록 합 니 다. 두 번 째 나무 에 대해 서도 dfs 를 한 번 진행 합 니 다. 모든 노드 u 에 대해 우 리 는 두 번 째 나무 에 기록 하고 u 라 는 노드 를 포함 하지 않 을 때 몇 개의 노드 가 u 에 포 함 된 시간 스탬프 에 나타 난 적 이 있 습 니까?나 타 났 기 때문에 이 점 이 덮 인 시간 스탬프 는 u 를 조상 으로 하 는 것 이 아니 라 는 것 을 알 수 있 습 니 다. 그 후에 우 리 는 두 번 째 나무 에서 u 의 자 나 무 를 겪 었 습 니 다. 그리고 역 사 를 끝 낸 후에 몇 개의 노드 가 u 에 포 함 된 시간 스탬프 에 나 타 났 는 지 다시 통계 합 니 다. 두 번 의 답 이 서로 줄 어 든 것 은 바로 두 개의 나무 에서 u 를 조상 으로 하 는 노드 수 입 니 다. 이 차 이 를 sum 으로 설정 합 니 다.이 노드 u 가 답 에 기여 한 것 은 (sum - 1) * (sum - 2) 입 니 다. u 에 포 함 된 시간 스탬프 의 결점 개 수 를 통계 할 때 우 리 는 트 리 배열 로 유지 할 수 있 습 니 다. 코드 는 다음 과 같 습 니 다.
#include
#include
#include
#include
using namespace std;
vector <int> edge[100010];
vector <int> pic[100010];
long long tree[10000000];
struct node{
int in,out;
}dfn[100010];
int cnt,In[100010],n;
long long ans;
int lowbit(int x){
return x&(-x);
}
void dfs1(int u,int fa){
dfn[u].in=++cnt;
for (int i=0;iint v=edge[u][i];
if (v==fa) continue;
dfs1(v,u);
}
dfn[u].out=cnt;
}
long long query(int x){
long long ans=0;
for (int i=x;i;i-=lowbit(i)){
ans+=tree[i];
}
return ans;
}
void add(int x,int val){
for (int i=x;i<=n;i+=lowbit(i)){
tree[i]+=val;
}
}
void dfs2(int u,int fa){
long long sum=query(dfn[u].out)-query(dfn[u].in-1);
add(dfn[u].in,1);
for (int i=0;iint v=pic[u][i];
if (v==fa) continue;
dfs2(v,u);
}
sum=query(dfn[u].out)-query(dfn[u].in-1)-sum-1;
ans+=(sum-1)*sum/2;
}
int main(){
scanf("%d",&n);
for (int i=1;iint u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
In[v]++;
}
for (int i=1;i<=n;i++)
if (!In[i]) dfs1(i,-1);
memset(In,0,sizeof(In));
for (int i=1;iint u,v;
scanf("%d%d",&u,&v);
pic[u].push_back(v);
In[v]++;
}
for (int i=1;i<=n;i++)
if (!In[i]) dfs2(i,-1);
printf("%lld
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.