一看这题简单啊 。。
于是写 。。
于是wa 。。。
传说中的暴栈 。。。
人工写 。。 对我来说还是挺难的 。。。
注释掉的就是暴栈的 。。
int start[maxn]; int end[maxn]; int vis[maxn]; int C[maxn]; int ans[maxn]; int ans1[maxn]; int ans2[maxn]; int stack[maxn]; int t, n; vector<int>v[maxn]; int lowbit(int x) { return x&(-x); } void add(int pos, int val) { for(; pos<=n; pos+=lowbit(pos)) C[pos] += val; } int query(int pos) { int s = 0; for(; pos; pos-=lowbit(pos)) s += C[pos]; return s; } /*void dfs(int u) { vis[u] = 1; ans1[u] = query(u-1); add(u, 1); for(int i=0; i<v[u].size(); i++) if(vis[ v[u][i] ]==0) { dfs( v[u][i] ); } ans[u] = query(u-1)-ans1[u]; }*/ void dfs(int u) { memset(C, 0, sizeof(C)); memset(vis, 0, sizeof(vis)); int top = 0; stack[top++] = u; vis[u] = 1; ans1[u] = query(u-1); add(u, 1); while(top) { int i, uu; u = stack[top-1]; for(i=0; i<v[u].size(); i++) { uu = v[u][i]; if(!vis[uu]) { stack[top++] = uu; ans1[uu] = query(uu-1); add(uu, 1); vis[uu] = 1; break; } } if( i==v[u].size() ) { top--; uu = stack[top]; ans[uu] = query(uu-1) - ans1[u]; } } } int main() { int p, a, b; while(scanf("%d%d", &n, &p), n) { t = 0; for(int i=1; i<=n; i++) v[i].clear(); for(int i=1; i<n; i++) { scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } dfs(p); for(int i=1; i<n; i++) printf("%d ", ans[i]); printf("%d\n", ans[n]); } return 0; }