题目描述
http://ac.jobdu.com/problem.php?pid=1541
直接模拟就好了,但是我的代码后面的样例要超时。。。不知道为什么,把cin , cout 改成 scanf 之后居然就变成 output limit exceed 了,奇怪。
算了,思路对的就行,懒得去搞了。
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<cstring> #include<climits> #include<queue> #include<map> #include<algorithm> using namespace std; struct node { int parent,left,right; int id,childsum; node():parent(-1),left(-1),right(-1),childsum(1){} }; node tree[1005]; int calChildSum(int rt) { if(rt==-1||tree[rt].childsum!=-1) return 0; int l=calChildSum(tree[rt].left); int r=calChildSum(tree[rt].right); tree[rt].childsum=l+r+1; return tree[rt].childsum; } int children(int rt) { if(rt==-1) return 0; return tree[rt].childsum; } void push_up(int rt) { if(rt==-1) return; tree[rt].childsum=1+children(tree[rt].left)+children(tree[rt].right); } void rotate(int rt) { if(rt==-1||tree[rt].parent==-1) return; int p=tree[rt].parent; if ( rt==tree[p].left) { int r=tree[rt].right; tree[p].left=r; if(r!=-1) tree[r].parent=p; tree[rt].right=p; } else { int l=tree[rt].left; tree[p].right=l; if(l!=-1) tree[l].parent=p; tree[rt].left=p; } int pp=tree[p].parent; tree[p].parent=rt; tree[rt].parent=pp; if(pp!=-1&&tree[pp].left==p) tree[pp].left=rt; else if (pp!=-1&&tree[pp].right==p) tree[pp].right=rt; push_up(p); push_up(rt); } int main() { int n; while(cin>>n) { for(int i=1;i<=n;i++) { tree[i].id=i; tree[i].left=tree[i].right=-1; tree[i].parent=-1; tree[i].childsum=-1; } for(int i=1;i<=n;i++) { tree[i].id=i; cin>>tree[i].left>>tree[i].right; if(tree[i].left!=-1) tree[tree[i].left].parent=i; if(tree[i].right!=-1) tree[tree[i].right].parent=i; } for(int i=1;i<=n;i++) calChildSum(i); int t; cin>>t; while(t--) { string op; int id; cin>>op>>id; if(op=="size") cout<<tree[id].childsum<<endl; else if (op=="rotate") rotate(id); else if (op=="parent") cout<<tree[id].parent<<endl; } } }