Codeforces 931D Peculiar apple-tree
4156 단어 CodeforcesACM 알고리즘
Once tree starts fruiting, there appears exactly one apple in each inflorescence. The same moment as apples appear, they start to roll down along branches to the very base of tree. Each second all apples, except ones in first inflorescence simultaneously roll down one branch closer to tree base, e.g. apple in a-th inflorescence gets to pa-th inflorescence. Apples that end up in first inflorescence are gathered by Arcady in exactly the same moment. Second peculiarity of this tree is that once two apples are in same inflorescence they annihilate. This happens with each pair of apples, e.g. if there are 5 apples in same inflorescence in same time, only one will not be annihilated and if there are 8 apples, all apples will be annihilated. Thus, there can be no more than one apple in each inflorescence in each moment of time.
Help Arcady with counting number of apples he will be able to collect from first inflorescence during one harvest.
Input
First line of input contains single integer number n (2 ≤ n ≤ 100 000) — number of inflorescences.
Second line of input contains sequence of n - 1 integer numbers p2, p3, ..., pn (1 ≤ pi i), where pi is number of inflorescence into which the apple from i-th inflorescence rolls down.
Output
Single line of output should contain one integer number: amount of apples that Arcady will be able to collect from first inflorescence during one harvest.
Examples
Input
3
1 1
Output
1
Input
5
1 2 2 2
Output
3
Input
18
1 1 1 4 4 3 2 2 2 10 8 9 9 9 10 10 4
Output
4
Note
In first example Arcady will be able to collect only one apple, initially situated in 1st inflorescence. In next second apples from 2nd and 3rd inflorescences will roll down and annihilate, and Arcady won't be able to collect them.
In the second example Arcady will be able to collect 3 apples. First one is one initially situated in first inflorescence. In a second apple from 2nd inflorescence will roll down to 1st (Arcady will collect it) and apples from 3rd, 4th, 5th inflorescences will roll down to 2nd. Two of them will annihilate and one not annihilated will roll down from 2-nd inflorescence to 1st one in the next second and Arcady will collect it.
제목: 나무 한 그루를 주고 가지마다 사과가 하나씩 있어요. 가지마다 사과 두 개가 떨어지면 이 두 개의 사과가 없어져요. 그리고 마지막으로 몇 개의 사과가 남았냐고 물어봐요.
문제풀이 사고방식: 처음에 나는 네가 각 지점(즉 아버지 노드) 아래에 몇 개의 하위 노드를 구하라고 한 줄 알았다. 그리고 2를 남긴 후에 상층의 아버지 노드에 전달했다.내가 신나게 코드를 다 두드린 후에 이 코드는 세 번째 사례도 통과하지 못했다. 그리고 나는 문제를 다시 보려고 했다. 수업을 해야 하기 때문에 나는 수업 시간에 이 문제의 해법을 생각해냈다.
내가 제목을 다시 자세히 보고 그 세 번째 견본을 그려낸 후에 나는 모든 깊이에 홀수 개의 사과가 있는지 짝수 개의 사과가 있는지를 구하고 둘에 대한 나머지를 얻었다.ffs는 한 번씩 뛰어다니며 깊이의 사과나무를 기록하고 마지막으로 화해를 판단한 다음에 돌아와서 두드린다.AC.
AC 코드 첨부
#include
#include
#include
using namespace std;
const int maxn=1e5+10;
int head[maxn],n,num[maxn],tot,m,k,vis[maxn];
struct Node{
int v,next;
}node[maxn*2];
void add(int u,int v){
node[tot].v=v;node[tot].next=head[u];
head[u]=tot++;
}
void dfs(int u,int deep){
if(deep>k) k=deep;
num[deep]++;
if(head[u]==-1) return ;
for(int i=head[u];~i;i=node[i].next){
int v=node[i].v;
if(!vis[v]){
vis[v]=1;
dfs(v,deep+1);
}
}
}
int main(){
int i,j;
tot=0;
k=0;
memset(head,-1,sizeof(head));
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
scanf("%d",&n);
for(i=2;i<=n;i++){
scanf("%d",&m);
add(m,i);
}
dfs(1,1);
int ans=0;
for(i=1;i<=k;i++){
if(num[i]){
ans+=num[i]%2;
}
}
printf("%d
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.