天梯赛树学合集

天梯赛关于树的知识考的还是就比较多的

1.PTA | 程序设计类实验辅助教学平台

#include<bits/stdc++.h>
using namespace std;
int n;
int root,a[2000];
int f=1,g=1;
void dfs1(int l,int r){if(f==0) return;int bal=a[l];if(r-l+1<=2) return;for(int i=l+1;i<=r;i++){if(a[i]<bal&&i<r) continue;else if(a[i]<bal&&i==r){dfs1(l+1,r);}else{for(int j=i+1;j<=r;j++){if(a[j]<bal){f=0;break;}}if(f==0) return;dfs1(l+1,i-1);dfs1(i,r);break;}}return;
}
void dfs2(int l,int r){if(g==0) return;int bal=a[l];if(r-l+1<=2) return;for(int i=l+1;i<=r;i++){if(a[i]>=bal&&i<r) continue;else if(a[i]>=bal&&i==r){dfs2(l+1,r);}else{for(int j=i+1;j<=r;j++){if(a[j]>=bal){g=0;break;}}if(g==0) return;dfs2(l+1,i-1);dfs2(i,r);break;}}return;
}
void dfs3(int l,int r){int bal=a[l];if(l>r) return;if(l==r){if(l==1) cout<<bal;else cout<<bal<<" ";return;}int id=l;for(int i=l+1;i<=r;i++){if(a[i]<bal){id=i;continue;}else break;}dfs3(l+1,id);dfs3(id+1,r);if(l==1) cout<<a[l];else cout<<a[l]<<" ";return;
}
void dfs4(int l,int r){int bal=a[l];if(l>r) return;if(l==r){if(l==1) cout<<bal;else cout<<bal<<" ";return;}int id=l;for(int i=l+1;i<=r;i++){if(a[i]>=bal){id=i;continue;}else break;}dfs4(l+1,id);dfs4(id+1,r);if(l==1) cout<<a[l];else cout<<a[l]<<" ";return;
}
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];//judgedfs1(1,n);//判断升序dfs2(1,n);if(g==0&&f==0){cout<<"NO";}else{cout<<"YES"<<endl;if(f){dfs3(1,n);}else{dfs4(1,n);}}
}

2.建树：PTA | 程序设计类实验辅助教学平台

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[50],b[50];
pair<int,int> edge[60];
int rr;
queue<int> q;
int dfs(int l1,int r1,int l2,int r2){if(l1>r1||l2>r2) return -1;if(l1==r1){edge[a[l1]].first=edge[a[l1]].second=-1;return a[l1];} int root=a[r1];int bx=-1;for(int i=l2;i<=r2;i++){if(root==b[i]){bx=i;break;}}if(bx==l2){edge[root].first=-1;edge[root].second=dfs(l1,r1-1,l2+1,r2);}else if(bx==r2){edge[root].second=-1;edge[root].first=dfs(l1,r1-1,l2,r2-1);}else{edge[root].first=dfs(l1,l1+bx-l2-1,l2,bx-1);edge[root].second=dfs(l1+bx-l2,r1-1,bx+1,r2);}return root;
}
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];//建树dfs(1,n,1,n);rr=a[n];q.push(rr);int cnt=0;while(!q.empty()){int yy=q.front();q.pop();cnt++;if(cnt==n) cout<<yy;else cout<<yy<<" ";if(edge[yy].first!=-1) q.push(edge[yy].first);if(edge[yy].second!=-1) q.push(edge[yy].second);}
}

3.直接根据后序遍历求：PTA | 程序设计类实验辅助教学平台、

按照后序遍历的顺序模拟即可，AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,ans=1;
int a[N],b[N],top=1;
void dfs(int x){if(x<=n){dfs(x*2);dfs(x*2+1);	b[x]=a[top++];}	
}
int main()
{int i,j;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);}dfs(1);for(i=1;i<=n;i++){if(i!=1) printf(" ");printf("%d",b[i]);}
}

4.数学+树状数组：PTA | 程序设计类实验辅助教学平台

这题质量十分不错，首先，我们知道对于一个树的DFS序一共是每一个子树的数量的阶乘相乘，当我们能确定一共有多少个逆序对后，我们会发现一个逆序对就是先遍历的值更大，进一步，我们可以分成两种情况，一种是如果在其链上一个值比他大那么它的贡献就是逆序对的个数，否则就是逆序对的1/2.

现在考虑怎么求，第一种情况比较简单，我们DFS一下顺便维护一个基于值的树状数组即可，对于第二种，我们可以考虑互补的情况，也就是除了那个点的子树一共包含了多少点，然后再减去它的链上的点及高度即可，我们通过预处理即可完成。

下面是AC代码（注意快速幂记得开LL）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//快速幂注意long long
ll mod=1e9+7;
ll n,r;
ll fac[300010];
vector<ll> edge[300010];
ll dpsum[300010],dep[300010];
ll fen[300100];
ll sum1,sum2;
ll cnt=1;
ll tr[300010];
void init(int n) {fac[0] = 1;for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;b>>=1;a=a*a%mod;}return res;
}ll lowbit(ll x){return x&-x;
}
void add(ll pos,ll v){for(ll i=pos;i<=n;i+=lowbit(i)){tr[i]+=v;tr[i]%=mod;}
}
ll ask(ll pos){ll num=0;for(ll i=pos;i;i-=lowbit(i)){num+=tr[i];num%=mod;}return num;
}
void dfs1(ll x,ll cnt,ll fa){dep[x]=cnt;for(int i=0;i<edge[x].size();i++){ll u=edge[x][i];if(u==fa) continue;fen[x]++;dfs1(u,cnt+1,x);}
}
void dfs2(ll x,ll fa){dpsum[x]=1;for(int i=0;i<edge[x].size();i++){ll u=edge[x][i];if(u==fa) continue;dfs2(u,x);dpsum[x]+=dpsum[u];dpsum[x]%=mod;}
}
void dfs3(ll x,ll fa){add(x,1);sum1+=dep[x]-ask(x-1);sum1%=mod;for(int i=0;i<edge[x].size();i++){ll u=edge[x][i];if(u==fa) continue;dfs3(u,x);}add(x,-1);
}
int main(){cin>>n>>r;init(n);for(int i=1;i<n;i++){ll u,v;cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}dfs1(r,0,-1);dfs2(r,-1);for(int i=1;i<=n;i++){ll www=1;cnt=cnt*fac[max(www,fen[i])]%mod;}//统计有多少个第一类节点dfs3(r,-1);for(ll i=1;i<=n;i++){sum2+=n-dpsum[i]-dep[i];sum2%=mod;}cout<<(cnt*sum1%mod+cnt*sum2%mod*qpow(4,mod-2)%mod+mod)%mod;
}

5.树+DFS：PTA | 程序设计类实验辅助教学平台

很有意思的一道题，感觉算得上L2里最难也是最有意思的一个了。

建议先自己画一个图模拟一遍，会发现直观了很多：我们从上往下看，第一排就是max已经确定，对于第二排，我们也是知道了这两个值，但是不确定其顺序，假如可以确定对于下一层也是同样的问题，因此我们考虑递归求解

我们的问题就是如何求解顺序，很自然的，我们可以分别都试一下，但是这样时间复杂度比较高，其实我们可以发现有一种情况是一定可以确定的，那就是下面的max>上面的min，其他我们就分别试一下即可，然后递归求解，具体AC代码见下：

#include<bits/stdc++.h>
using namespace std;
int k,x;
vector<int> a[20];
int tr[1000000];
int dfs(int fa,int cnt,int l,int r,int l1,int r1){if(cnt>k) return 1;if(l>r) swap(l,r);if(r<max(a[cnt][l1],a[cnt][r1])||l<min(a[cnt][l1],a[cnt][r1])) return 0;else if(l>=max(a[cnt][l1],a[cnt][r1])){int f=1;tr[fa*2]=l,tr[fa*2+1]=r;if(!dfs(fa*2,cnt+1,a[cnt][l1],l,2*l1,2*l1+1)||!dfs(fa*2+1,cnt+1,a[cnt][r1],r,2*r1,2*r1+1)) f=0;if(!f){tr[fa*2]=r,tr[fa*2+1]=l;if(!dfs(fa*2,cnt+1,a[cnt][l1],r,2*l1,2*l1+1)) return 0;if(!dfs(fa*2+1,cnt+1,a[cnt][r1],l,2*r1,2*r1+1)) return 0;}}else{if(a[cnt][l1]>a[cnt][r1]){tr[fa*2]=r,tr[fa*2+1]=l;if(!dfs(fa*2,cnt+1,a[cnt][l1],r,2*l1,2*l1+1)||!dfs(fa*2+1,cnt+1,a[cnt][r1],l,2*r1,2*r1+1)) return 0;}else{tr[fa*2]=l,tr[fa*2+1]=r;if(!dfs(fa*2,cnt+1,a[cnt][l1],l,2*l1,2*l1+1)||!dfs(fa*2+1,cnt+1,a[cnt][r1],r,2*r1,2*r1+1)) return 0;}}return 1;
}
int main(){cin>>k;for(int i=k;i>=1;i--){for(int j=1;j<=pow(2,i-1);j++){cin>>x;a[i].push_back(x);}}cin>>x;a[1].push_back(x);if(a[1][0]>a[1][1]){cout<<"No Solution";return 0;}tr[1]=x;if(!dfs(1,2,a[1][0],a[1][1],0,1))cout<<"No Solution";else{for(int i=pow(2,k-1);i<=pow(2,k)-1;i++){tr[i*2]=tr[i];tr[i*2+1]=a[k][i-pow(2,k-1)];}for(int i=pow(2,k);i<=pow(2,k+1)-1;i++){if(i!=pow(2,k+1)-1) cout<<tr[i]<<" ";else cout<<tr[i];}}
}