題目鏈接：http://codeforces.com/contest/746/problem/G
mamaya，不知道YY了一個什么做法就這樣過去了啊 2333
?
首先我顯然可以隨便構造出一棵樹滿足他所給出的深度要求。
但是他還對于葉子節點的數目有要求。
考慮首先構造一棵樹最大化在滿足給出的深度條件下最大化葉子節點的個數。
顯然對于每一層的節點讓它們的父親都指向上一層的同一個點的話就會有最多的葉子節點。
?
好，接下來考慮如何減少葉子結點。
我就是隨便貪心搞的(也許可以被叉？)
按照深度從小到大枚舉所有的點，如果這個點$x$是葉子節點，找到他的上一層是某一個也是葉子節點的點$y$,并將$x$的父親修改為$y$,同時還要注意到修改父親之后，$x$原本的父親也可能再度變回葉子節點。這些東西都用一個$vector$來維護就可以了。
?
復雜度：${O(n)}$
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001000 10 #define llg int 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,deep[maxn],c[maxn],a[maxn],du[maxn],dad[maxn],t,k,db[maxn],tot; 13 vector<llg>d[maxn]; 14 15 inline int getint() 16 { 17 int w=0,q=0; char c=getchar(); 18 while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 19 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w; 20 } 21 22 int main() 23 { 24 yyj("G"); 25 cin>>n>>t>>k; 26 for (llg i=1;i<=t;i++) a[i]=getint(),c[i]=a[i]; 27 llg p=1; 28 db[0]=1; 29 for (llg i=2;i<=n;i++) 30 { 31 if (c[p]==0) p++; 32 dad[i]=db[p-1]; deep[i]=p; 33 du[db[p-1]]++; 34 if (!db[p]) db[p]=i; 35 c[p]--; 36 } 37 for (llg i=1;i<=n;i++) if (!du[i]) {d[deep[i]].push_back(i); tot++;} 38 if (tot<k) {cout<<-1; return 0;} 39 for (llg i=1;i<=n;i++) 40 if (!du[i]) 41 { 42 if (tot==k) break; 43 if (d[deep[i]-1].size()!=0) 44 { 45 du[dad[i]]--; 46 if (du[dad[i]]==0){ tot++; d[deep[dad[i]]].push_back(dad[i]);} 47 du[d[deep[i]-1][d[deep[i]-1].size()-1]]++; 48 tot--; 49 dad[i]=d[deep[i]-1][d[deep[i]-1].size()-1]; 50 d[deep[i]-1].pop_back(); 51 } 52 } 53 if (tot!=k) {cout<<-1; return 0;} 54 cout<<n<<endl; 55 for (llg i=2;i<=n;i++) printf("%d %d\n",dad[i],i); 56 return 0; 57 }
?
