[平衡樹]HNOI2004 寵物收養所 pet

題目描述

最近，阿Q開了一間寵物收養所。收養所提供兩種服務：收養被主人遺棄的寵物和讓新的主人領養這些寵物。每個領養者都希望領養到自己滿意的寵物，阿Q根據領養者的要求通過他自己發明的一個特殊的公式，得出該領養者希望領養的寵物的特點值a（a是一個正整數，a<2^31），而他也給每個處在收養所的寵物一個特點值。這樣他就能夠很方便的處理整個領養寵物的過程了，寵物收養所總是會有兩種情況發生：被遺棄的寵物過多或者是想要收養寵物的人太多，而寵物太少。

1．被遺棄的寵物過多時，假若到來一個領養者，這個領養者希望領養的寵物的特點值爲a，那麼它將會領養一隻目前未被領養的寵物中特點值最接近a的一隻寵物。（任何兩隻寵物的特點值都不可能是相同的，任何兩個領養者的希望領養寵物的特點值也不可能是一樣的）如果有兩隻滿足要求的寵物，即存在兩隻寵物他們的特點值分別爲a-b和a+b，那麼領養者將會領養特點值爲a-b的那隻寵物。
2．收養寵物的人過多，假若到來一只被收養的寵物，那麼哪個領養者能夠領養它呢？能夠領養它的領養者，是那個希望被領養寵物的特點值最接近該寵物特點值的領養者，如果該寵物的特點值爲a，存在兩個領養者他們希望領養寵物的特點值分別爲a-b和a+b，那麼特點值爲a-b的那個領養者將成功領養該寵物。

一個領養者領養了一個特點值爲a的寵物，而它本身希望領養的寵物的特點值爲b，那麼這個領養者的不滿意程度爲abs(a-b)。

GZOI2011 Rail 解題報告

第四題（40分）

提交文件：Rail.exe

輸入文件：Rail.in

輸出文件：Rail.out

題目描述：

你所在的省剛獲得國家撥款興建高鐵，高鐵的起止城市是國家選定的，中途可能經過若干城市。根據國家撥款的政策，國家將負擔費用最大的兩個區間，其餘的必須由省負擔。假如高鐵線路中途只經過一個城市，國家只負擔費用較大的區間。假如是直達的，國家將不負擔任何費用。

你被省裡選定作為這個項目的總工程師，你必須規劃出一條高鐵線路，使得省負擔的費用最少。當然，路線上每個城市最多只經過一次。

GZOI2011 Pack 解題報告

第一題（20分）

提交文件：Pack.exe

輸入文件：Pack.in

輸出文件：Pack.out

 
題目描述：

你在一個組合式傢俱廠工作，這種組合式傢俱由各種形狀不同的組件組成，例如：

图1 三种不同形状的组件

這些組件生產出來後將被自動裝箱，組件按生產的次序落下，第一個組件落在箱子底部，其後的組件依次落下，直至組件接觸到之前裝入的組件或箱子底部。例如，假設組件按圖1從左至右的次序生產出來，裝箱結果將如圖2左所示。假如按圖1從右至左的次序生產出來，裝箱結果將如圖2右所示。

                 圖2 不同的生產次序導致兩種不同的裝箱結果

由於箱子高度有限，如圖2左，三個組件已經超過了箱子的高度，這種情況第三個組件及之後的組件需要用新的箱子來裝。

你的工作是為自動裝箱系統編寫程序，根據組件生產的次序，輸出裝完這些組件後，每個箱子的組件堆疊的高度。

GDOI2011 樂譜變調 music 解題報告

五、樂譜變調（30分 1-4資料5分，最後一個資料10分)

輸入文件：music.in

輸出文件：music.out

【問題描述】

大家應該聽過很多美妙動聽的歌曲，也曾經在卡拉OK中唱過不少歌曲。其實，很多歌曲的調子都經過了變調，因為很多歌曲原來的調子一般都偏高，需要把調適當降低，才適合一般人歌唱。現在請你編程解決這個變調的問題，把一個曲譜從原來的調子基礎上，升高或降低若干個調，變成一個新的曲譜。

【音階】

相信大家都見過電子琴，也聽過電子琴，琴中的每個白色鍵，代表的是簡譜中的1,2,3,4,5,6,7的音階，用字母代表即為 C,D,E,F,G,A,B，見下圖：

此外，上面的黑鍵表示半音，按照上圖，從左邊到右邊的5個黑鍵代表的半音為：#C,#D,#F,#G,#A

由最左邊的音階C數起到第七個音階B，中間的黑鍵和鍵，均處於一個基準八度區域，在B右邊的琴鍵，比原來的音階高一個八度區域，稱為高八度區域； C音階左邊的琴鍵（圖片沒有顯示），比原來的音階低一個八度區域，稱為低八度區域。

【樂譜】

一個歌曲的樂譜，包括音階、節奏、小節線、休止符等元素，這裡為了簡單表示，只保留音階這一元素，節奏、小節線、休止符不在此題目中展現。

樂譜中的每個音階，可以用C,D,E,F,G,A,B,#C,#D,#F,#G,#A 表示。

在樂譜中會牽涉到八度區域的遷移問題，我們使用 “>”、“<” 來變化當前的八度區域。其中“>”表示提高當前八度區域（例如從低八度區域=>基準八度區域），“<”表示降低當前八度區域(例如高八度區域=>基準八度區域)。樂譜一開始的時候，當前八度區域為基準八度區域。

【樂譜變調】

對一個樂譜，提高或者降低N個半音的操作，成為樂譜變調。

首先，對於一個八度區域中，以下音階均相隔一個半音。

C,#C,D,#D,E,F,#F,G,#G,A,#A,B

然後，B音階比高它一個八度區域的C音階，相隔一個半音

變調就是一個簡單的升降音階的操作，只要數著半音階個數修改音階即可。例如，C音階提高6個半音，數過去就是#F，B音階提高4個音階，則為下一個八度區域的 #D 音階，同理，#F降6個半音階（升-6個半音）則為C。

【輸入格式】

輸入第一行字元串，包含上面的各個音階，以及>/<符號，表示一個樂譜，樂譜字元串長度<=200，沒有空格和其他字元串。

輸入第二行為整數N (-16<=N<=16) ，表示升多少個半音

【輸出格式】

輸出為一行字元串，代表樂譜。

【輸入樣例】

CDEFGAB>C

2

【輸出樣例】

DE#FGAB>#CD

【分析】

看著題目挺花哨，其實很簡單，就是一個模擬，只要讀請題目一般都能滿分。

【我的代碼】

裸代碼

C++语言: Codee#25363

001 /*
002 *Problem: GDOI2011 Music
003 *Author: Yee-fan Zhu
004 *Email: zyfworks@gmail.com
005 */
006 #include <cstdlib>
007 #include <iostream>
008 #include <cstdio>
009 #include <cstring>
010 using namespace std;
011 int N;
012
013 int num[300];
014 int M=0;
015
016 int Hash(char a,char b)
017 {
018     if(a=='C' && b=='0') return 1;
019     if(a=='#' && b=='C') return 2;
020     if(a=='D' && b=='0') return 3;
021     if(a=='#' && b=='D') return 4;
022     if(a=='E' && b=='0') return 5;
023     if(a=='F' && b=='0') return 6;
024     if(a=='#' && b=='F') return 7;
025     if(a=='G' && b=='0') return 8;
026     if(a=='#' && b=='G') return 9;
027     if(a=='A' && b=='0') return 10;
028     if(a=='#' && b=='A') return 11;
029     if(a=='B' && b=='0') return 12;
030     return 0;
031 }
032
033 void print(int a)
034 {
035     if(a==1) printf("C");
036     if(a==2) printf("#C");
037     if(a==3) printf("D");
038     if(a==4) printf("#D");
039     if(a==5) printf("E");
040     if(a==6) printf("F");
041     if(a==7) printf("#F");
042     if(a==8) printf("G");
043     if(a==9) printf("#G");
044     if(a==10) printf("A");
045     if(a==11) printf("#A");
046     if(a==0) printf("B");
047 }
048
049 void init()
050 {   
051     char str[300];
052     scanf("%s\n%d\n",&str,&N);
053     int len=strlen(str);
054     int top=0;
055     int now=2;
056     while(top<len)
057     {
058         char c=str[top];
059         if(c=='#')
060         {
061             int res=(now-1)*12+Hash(c,str[top+1]);
062             num[++M]=res;
063             top+=2;
064             continue;
065         }
066         if(c=='>')
067         {
068             now++;
069             top++;
070             continue;
071         }
072         if(c=='<')
073         {
074             now--;
075             top++;
076             continue;
077         }
078        
079         int res=(now-1)*12+Hash(c,'0');
080         num[++M]=res;
081         top++;
082         continue;
083     }
084 }
085
086 void work()
087 {
088     for (int i=1;i<=M;i++)
089         num[i]+=N;
090     int now=2;
091     int up=25;
092     int down=12;
093     for(int i=1;i<=M;i++)
094     {
095         int tmp=num[i];
096         if(tmp<=down)
097         {
098             now--;
099             down-=12;
100             up-=12;
101             printf("<");
102             print(tmp%12);
103             continue;
104         }
105         if(tmp>=up)
106         {
107             now++;
108             down+=12;
109             up+=12;
110             printf(">");
111             print(tmp%12);
112             continue;
113         }
114         print(tmp%12);
115     }
116 }
117
118 int main()
119 {
120     freopen("music.in","r",stdin);
121     freopen("music.out","w",stdout);
122     init();
123     work();
124     return 0;
125 }

【BFS】GZOI2011廣州2011選拔賽：理財年代 money 解題報告

【問題描述】

最近通貨膨脹很厲害，CPI跑得比銀行利息要快，要抗通脹，又要避風險，其中一種很好的方式，就是購買銀行發行的理財產品。雖然理財產品的利息比銀行定期要高，而且沒有風險，但是，購買理財產品需要一定的資金門檻，而且還要保證吧錢存入一定時間不能取出來，因此也是有一定的限制的。

小郭很喜歡研究銀行的理財產品，她計劃在2011年拿10萬元進行理財產品的投資，為了簡單方便，她在2011年每次投資理財產品時，都是把這筆資金和之前購買理財產品產生的所有利息投入進去，希望在年底獲取最高的利潤。

【理財產品】

一個理財產品有如下要素：

資金門檻：至少要投入多少資金；

發行時間：該理財產品的購買時間；

投資天數：資金存放的天數，

年利息：該理財產品如果存放一年365天能獲取的利息。

由於郭小姐選擇的所有理財產品的門檻都是10萬以內，因此理財產品就剩下的3個要素。

例如，A1理財產品，發行時間是3月1日，投資天數為30天，年利息為 3.5%，那麼，如果10萬元購買該產品，那麼在30天后，也就是3月30日收市後，她可以獲得的資金為：

`100000*(1+0.035*30/365)=100287.67元 （四捨五入，保留2位小數）

然後，她就可以吧100287.67元這筆資金，購買3月31日或之後發行的任何理財產品。

郭小姐在這一年內不斷把本金和利息一起全額地購買理財產品，希望在2012年到來之前獲得最高的收益。如果購買的兩個理財產品之間有時間間隔，那麼這筆錢就不能產生利潤（銀行活期利息太低，利潤可以忽略）。請問她這年內，能通過購買理財產品，最多獲取多少錢呢？

【輸入格式】

第一行是整數N(1<=N<=15)，代表理財產品的數目

下面N行為3個由空格隔開的字元串 A B C

A代表發行時間，格式為MMDD（兩位月兩位日），例如4月1日則為0401，10月2日則為1002

B (整數)，代表投資天數，範圍是[10,300]

C (最多2位的小數)，代表百分之幾的年利息，範圍是[3,30]

輸入資料保證 發行時間+投資天數不會超過2012年。

【輸出格式】

輸出只有一行，為年底最多可獲得的連本帶利的資金數目，保留2位小數

【輸入樣例】

3

0101 100 4.5

0201 30 5

0402 50 7.8

【例子分析】

例子中的3個理財產品，只能購買1號產品，或者連續購買2號、3號理財產品。

購買1號理財產品的收益為 100000*(1+0.045*100/365)=101232.88

購買2/3號理財產品的收益為：

購買2號產品後總資金： 100000*(1+0.05*30/365)=100410.96

再購買3號產品後總資金： 100410.96*(1+0.078*50/365)=101483.84

因此最高收益為 101483.84

【輸出樣例】

101483.84

【分析】

本題是廣州NOI選拔賽中比較簡單的一道，可以用BFS廣度優先搜索做。由於N很小、而且減枝十分有效，所以隊列會很小。

本題易錯地方有：

1) 日期的轉換和判斷

2) 利息的計算

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int N;
class Money
{
public:
    int Mon;
    int Days;
    int Day1;
    int Day2;
    int Time;
    double Rate;
}M[30];

int days(int b,int c) 
{ 
    int d=0; 
    if(b==1) d=c; 
    if(b==2) d=31+c; 
    if(b==3) d=60+c; 
    if(b==4) d=91+c; 
    if(b==5) d=121+c; 
    if(b==6) d=152+c; 
    if(b==7) d=182+c; 
    if(b==8) d=213+c; 
    if(b==9) d=244+c; 
    if(b==10) d=274+c; 
    if(b==11) d=305+c; 
    if(b==12) d=335+c; 
    return d; 
} 

int cmp(const void *a,const void *b)
{
    class Money *c=(class Money *)a;
    class Money *d=(class Money *)b;
    if(c->Day1!=d->Day1)
        return c->Day1-d->Day1;
    return c->Day2-d->Day2;
}

void init()
{
    scanf("%d\n",&N);
    int tmp1,tmp2;
    char ch1,ch2;
    for (int i=1;i<=N;i++)
    {
        scanf("%c%c",&ch1,&ch2);
        tmp1=(ch1-'0')*10+ch2-'0';
        scanf("%c%c",&ch1,&ch2);
        tmp2=(ch1-'0')*10+ch2-'0';
        M[i].Mon=tmp1;
        M[i].Days=tmp2;
        M[i].Day1=days(tmp1,tmp2);
        scanf("%d %lf\n",&M[i].Time,&M[i].Rate);
        M[i].Day2=M[i].Day1+M[i].Time-1;
    }
    qsort(M+1,N,sizeof(M[0]),cmp);
}

class QUEUE
{
public:
    double money;
    int pos;
    int day;
}Q[100000];

double GetMoney(double ben,int num)
{
    double res=ben;
    double rate=double(1)+M[num].Rate*(double(M[num].Time)/double(365))/(double(100));
    res=res*rate;
    return res;
}

void bfs()
{
    double S=0;
    int head=N;
    int rear=0;
    for (int i=1;i<=N;i++)
    {
        Q[i-1].pos=i;
        Q[i-1].money=GetMoney(double(100000),i);
        Q[i-1].day=M[i].Day2+1;
    }
   
    double tm;
    int td;
    int tp;
    while(rear<head)
    {
        tm=Q[rear].money;
       
        if(tm>S)
            S=tm;
       
        td=Q[rear].day;
        tp=Q[rear].pos;
        for(int i=tp+1;i<=N;i++)
        {
            if(M[i].Day1>=td)
            {
                Q[head].money=GetMoney(tm,i);
                Q[head].pos=i;
                Q[head].day=M[i].Day2+1;
                head++;
            }
        }
        rear++;
    }
    printf("%.2lf\n",S);
}


int main()
{
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    init();
    bfs();
    return 0;
}

GZOI2011廣州NOI省選：簡易計算器 calculator 解題報告

【問題描述】相信大家都用過計算器，一般來說，計算機都可以計算簡單的加、減、乘、除這幾種運算。簡易計算器的功能和一般的計算器一樣，只是它更加簡單，只能處理整數運算，也就是說，它沒有小數點按鈕，並且它的除法運算是整除運算。現在，我們給出簡易計算器上的按鈕序列，請你編程序，模擬簡易計算器的功能，輸出最終的結果。
      【計算器組成】簡易計算器由以下按鈕組成：數字按鈕： 0 1 2 3 4 5 6 7 8 9運算按鈕： + - * /等於號按鈕：=正負轉換按鈕：+/-為了表述方便，+/- 按鈕用 F 表示 ，
 【計算器邏輯處理】
    計算器內存有3個值，M1，M2，OP，STM1為計算器的左運算值，初始值為0M2為計算器的右運算值，初始值0OP為計算器的當前運算符，初始值為空ST為狀態標記，初始值為0
 狀態裝換邏輯如下：
 ST=0 (M1/OP輸入態)：顯示值：M1
 輸入數字N ：M1=N ，轉 ST=1狀態
 輸入F ：M1=-M1，轉 ST=0狀態
 輸入運算符：OP=運算符，轉ST=2狀態
 輸入“=”：轉 ST=0狀態
 ST=1 (M1+/OP輸入態)：顯示值：M1
 輸入數字N ：如果M1>=0則 M1=M1*10+N 否則M1=M1*10-N;轉 ST=1狀態；
 輸入F ：M1=-M1，轉 ST=1狀態；
 輸入運算符：OP=運算符，轉ST=2狀態
 輸入“=”：轉 ST=0狀態
 ST=2 (OP/M2輸入態)：顯示值：M1
 輸入數字N：M2=N，轉ST=3狀態;輸入F：M2=0，轉 ST=3狀態；
 輸入運算符：OP=運算符，轉ST=2狀態
 輸入“=”：
 轉 ST=0狀態
 ST=3 (M2+/OP輸入態)：顯示值：M2
 輸入數字N：如果M2>=0則 M2=M2*10+N 否則M2=M2*10-N；轉ST=3狀態；輸入F：M2=-M2，轉 ST=3狀態；
 輸入運算符：M1=[M1][OP][M2] 的值OP=運算符；轉ST=2狀態
 輸入“=”： M1=[M1][OP][M2] 的值轉ST=0狀態
 【輸入格式】輸入只有一行，表示在計算器輸入的按鈕，長度<=100，裡面只包含如下字符 :0123456789+-*/=F輸入數據保證不會出現除以0的情況，運算過程中各個內存的值的範圍在[-10000000, 10000000] 以內

 【輸出格式】
    輸出包含一行整數，表示最後在計算器顯示的結果
 【輸入樣例】
        123=*2F-+/3+-=
        【輸出樣例】
 -82

 【分析】
字符串處理題目，由於各種狀態之間的來回跳換，所以用遞歸實現比較方便。由於數據不大，暴力的遞歸不成問題。

時間複雜度：O（length）。
            length表示字符串的長度。


 【我的代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
char str[102];
int OP;
int top=0;
int M1=0,M2=0;
int show;
int len;
int tmp;
void deal0();
void deal1();
void deal2();
void deal3();

int Getop(char op)
{
    if(op=='+')
        return 1;
    if(op=='-')
        return 2;
    if(op=='*')
        return 3;
    if(op=='/')
        return 4;
    if(op=='F')
        return 5;
    if(op=='=')
        return 6;
    return 0;
}

void check()
{
    if(top==len)
    {
        printf("%d\n",show);
        exit(0);
    }
    return;
}

void deal0()
{
    show=M1;
    check();
    tmp=0;
    if(Getop(str[top])==0)
    {
        while(Getop(str[top])==0 &&top<len)
        {
            tmp=tmp*10+str[top]-'0';
            top++;
        }
        M1=tmp;
        deal1();
        return;
    }
    if(Getop(str[top])==5)
    {
        M1=-M1;
        top++;
        deal0();
        return;
    }
    if(Getop(str[top])>=1 && Getop(str[top])<=4)
    {
        OP=Getop(str[top]);
        top++;
        deal2();
        return;
    }
    if(Getop(str[top])==6)
    {
        top++;
        deal0();
        return;
    }
}

void deal1()
{
    show=M1;
    check();
    tmp=0;
    if(Getop(str[top])==0)
    {
        while(Getop(str[top])==0 && top<len)
        {
            tmp=tmp*10+str[top]-'0';
            top++;
        }
        if(M1>=0)
            M1=M1*10+tmp;
        else
            M1=M1*10-tmp;
        deal1();
        return;
    }
    if(Getop(str[top])==5)
    {
        M1=-M1;
        top++;
        deal1();
        return;
    }
    if(Getop(str[top])>=1 && Getop(str[top])<=4)
    {
        OP=Getop(str[top]);
        top++;
        deal2();
        return;
    }
    if(Getop(str[top])==6)
    {
        top++;
        deal0();
        return;
    }
}

void deal2()
{
    show=M1;
    check();
    tmp=0;
    if(Getop(str[top])==0)
    {
        while(Getop(str[top])==0 && top<len)
        {
            tmp=tmp*10+str[top]-'0';
            top++;
        }
        M2=tmp;
        deal3();
        return;
    }
    if(Getop(str[top])==5)
    {
        M2=0;
        top++;
        deal3();
        return;
    }
    if(Getop(str[top])>=1 && Getop(str[top])<=4)
    {
        OP=Getop(str[top]);
        top++;
        deal2();
        return;
    }
    if(Getop(str[top])==6)
    {
        top++;
        deal0();
        return;
    }
}

void deal3()
{
    show=M2;
    check();
    tmp=0;
    if(Getop(str[top])==0)
    {
        while(Getop(str[top])==0 && top<len)
        {
            tmp=tmp*10+str[top]-'0';
            top++;
        }
        if(M2>=0)
            M2=M2*10+tmp;
        else
            M2=M2*10-tmp;
        deal3();
        return;
    }
    if(Getop(str[top])==5)
    {
        M2=-M2;
        top++;
        deal3();
        return;
    }
    if(Getop(str[top])>=1 && Getop(str[top])<=4)
    {
        if(OP==1)
            M1=M1+M2;
        if(OP==2)
            M1=M1-M2;
        if(OP==3)
            M1=M1*M2;
        if(OP==4)
            M1=M1/M2;
        OP=Getop(str[top]);
        top++;
        deal2();
        return;
    }
    if(Getop(str[top])==6)
    {
        top++;
        //deal0();
        if(OP==1)
            M1=M1+M2;
        if(OP==2)
            M1=M1-M2;
        if(OP==3)
            M1=M1*M2;
        if(OP==4)
            M1=M1/M2;
        deal0();
        return;
    }
}

void init()
{
    std::ios::sync_with_stdio(false);
    scanf("%s\n",&str);
    len=strlen(str);
    return;
}

int main()
{
    freopen("calculator.in","r",stdin);
    freopen("calculator.out","w",stdout);
    init();
    deal0();
    return 0;
}
 
 
 【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	20	0.000 s	275 KB	0
2	正确	20	0.000 s	275 KB	0
3	正确	20	0.000 s	275 KB	0
4	正确	20	0.000 s	275 KB	0
5	正确	20	0.000 s	275 KB	0

运行完成
运行时间 0.002 s
平均内存使用 275 KB
测试点通过状况 AAAAA
得分：100
恭喜你通过了全部测试点!

[搜索]AHOI2009：飛行棋 fly 解題報告

Description

給出圓週上的若干個點，已知點與點之間的弧長，其值均爲正整數，並依圓周順序排列。

請找出這些點中有沒有可以圍成矩形的，並希望在最短時間內找出所有不重複矩形。

Input

第一行爲正整數N，表示點的個數，接下來N行分別爲這N個點所分割的各個圓弧長度

Output

所構成不重複矩形的個數

Sample Input

8 1 2 2 3 1 1 3 3

Sample Output

3

Hint

N<= 20

Source 

HAOI2009-2    2009年安徽NOI省選 第二試 第一題

【分析】 

省選中的水題，直接爆搜即可。

根據平面幾何的知識，構成矩形的充分條件是對邊相等。

由於數據量不大，深度優先搜索、廣度優先搜索均可，連開四層循環暴力枚舉都可以。

【我的代碼】
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int N;
int Q[5];
int S[21]={0};
int C[21];
int ans=0;

void init()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>C[i];
        S[i]=S[i-1]+C[i];
    }
}

void dfs(int deep,int num)
{
    if(deep==5)
    {
        if((S[N]-Q[2]-Q[3]-Q[4])==Q[3] && Q[2]==Q[4])
            ans++;
        return;
    }
    for (int i=num+1;i<=N;i++)
    {
        Q[deep]=S[i]-S[num];
        dfs(deep+1,i);
    }
}

int main()
{
    freopen("fly.in","r",stdin);
    freopen("fly.out","w",stdout);
    init();
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}