乱搞
一个节点如果有值x那么可以确定他的上界是x，否则他的父节点值为y，上界就是y-1 如果一个节点的上界x，且可以确定x-1个点的上界不超过x-1，那么显然这个节点的值就是可以确定的
上文是后来的想法，原来做这题的时候好像用了一个大致思想有点像但复杂很多的方法，不建议参考代码 code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long longusing namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}const int maxn = 1100000;struct edge{ int y,nex; edge(){} edge(int _y,int _nex){y=_y;nex=_nex;}}a[maxn]; int len,fir[maxn];int out[maxn];void ins(int x,int y) {a[++len]=edge(y,fir[x]); fir[x]=len;}struct node{ int x,i; node(){} node(int _x,int _i){x=_x;i=_i;}}s[maxn]; int tot;int n;bool cmp(node x,node y){return x.x<y.x;}int val[maxn];bool v[maxn]; int bel[maxn];int add[maxn],fa[maxn],siz[maxn],rt;void dfs(int x){ siz[x]=1; for(int k=fir[x];k;k=a[k].nex) { int y=a[k].y; dfs(y); siz[x]+=siz[y]; }}void solve(int x){ if(out[x]==1) { int y; for(int k=fir[x];k;k=a[k].nex) if(!val[a[k].y]) { y=a[k].y; break;} int k=val[x]-1; if(!v[k]) { while(k>0&&!v[k]&&!out[bel[k]]) k--; if(!v[k]) return ; } val[y]=k; solve(y); }}int main(){ read(n); len=0; memset(v,true,sizeof v); for(int i=1;i<=n;i++) { int x,y; read(x); read(y); if(x==i) fa[i]=0,rt=i; else fa[i]=x,ins(x,i); if(y) s[++tot]=node(y,i),val[i]=y,v[y]=false,bel[y]=i; else out[x]++; } if(!val[rt]) val[rt]=n,s[++tot]=node(rt,n),v[n]=false,bel[n]=rt; dfs(rt); sort(s+1,s+tot+1,cmp); int sum=0; for(int i=1;i<=n;i++) { node nw=s[i]; int k=siz[nw.i]; if(nw.x-(sum-add[nw.i])==k) solve(nw.i); sum+=k-add[nw.i]; add[fa[nw.i]]+=k; } for(int i=1;i<=n;i++) PRintf("%d/n",val[i]); return 0;}新闻热点
疑难解答
