常州规划网站,wordpress做的好的网站,建筑工程网络教育自我鉴定,泰安网站建设推广解析
做法很多的一道题
sol1
先求出dfs序#xff0c;离线下来#xff0c;然后按权值大小的顺序统计答案并插到对应的dfs序中
sol2
离散化后#xff0c;dfs过程中动态维护树状数组#xff0c;利用前后差值求出答案
sol3
树上dsu 就比较无脑了#xff0c;暴力维护即可…解析
做法很多的一道题
sol1
先求出dfs序离线下来然后按权值大小的顺序统计答案并插到对应的dfs序中
sol2
离散化后dfs过程中动态维护树状数组利用前后差值求出答案
sol3
树上dsu 就比较无脑了暴力维护即可 但是代码比前两个难写
sol4
权值线段树合并 这个做法在本题中确实是一点优势也没有 兼具了常数大和难编写的双重优势bushi
总的来说前两种做法比较推荐
代码
使用的是soltion1 别问我为什么当时还敲了个树剖和线段树上去
#includebits/stdc.h
using namespace std;
#define ll long long
const int N3e5100;
int n,m;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt-1;
void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}
int dfn[N],fa[N],top[N],pos[N],tim,dep[N],hson[N],siz[N];
void dfs1(int x,int f){fa[x]f;//printf(x%d f%d\n,x,f);siz[x]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dep[to]dep[x]1;dfs1(to,x);siz[x]siz[to];if(!hson[x]||siz[hson[x]]siz[to]) hson[x]to;}return;
}
void dfs2(int x,int tp){dfn[tim]x;pos[x]tim;top[x]tp;if(hson[x]) dfs2(hson[x],tp);for(int ifi[x];~i;ip[i].nxt){int top[i].to;//printf(x%d to%d\n,x,to);if(tofa[x]||tohson[x]) continue;dfs2(to,to);}return;
}
#define mid ((lr)1)
#define ls k1
#define rs k1|1
ll sum[N2],add[N2];
void pushup(int k){sum[k]sum[ls]sum[rs];
}
void Add(int k,int l,int r,ll v){add[k]v;sum[k]1ll*(r-l1)*v;return;
}
void pushdown(int k,int l,int r){ll oadd[k];add[k]0;if(!o) return;Add(ls,l,mid,o);Add(rs,mid1,r,o);return;
}
void change(int k,int l,int r,int x,int v){if(lr){sum[k]v;return;}pushdown(k,l,r);if(xmid) change(ls,l,mid,x,v);else change(rs,mid1,r,x,v);pushup(k);return;
}
void longchange(int k,int l,int r,int x,int y,int v){if(xlry){Add(k,l,r,v);return;}pushdown(k,l,r);if(xmid) longchange(ls,l,mid,x,y,v);if(ymid) longchange(rs,mid1,r,x,y,v);pushup(k);return;
}
ll ask(int k,int l,int r,int x,int y){if(xlry){//printf(k%d l%d r%d x%d y%d res%lld\n,k,l,r,x,y,sum[k]);return sum[k];}pushdown(k,l,r);ll res0;if(xmid) resask(ls,l,mid,x,y);if(ymid) resask(rs,mid1,r,x,y);//printf(k%d l%d r%d x%d y%d res%lld\n,k,l,r,x,y,res);return res;
}
ll sumquery(int x,int y){ll res0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);resask(1,1,n,pos[top[x]],pos[x]);xfa[top[x]];}if(dep[x]dep[y]) swap(x,y);resask(1,1,n,pos[y],pos[x]);return res;
}
struct P{int id,v;bool operator (const P y)const{return vy.v;}
}a[N];
int ans[N];
int main(){memset(fi,-1,sizeof(fi));scanf(%d,n);for(int i1;in;i){scanf(%d,a[i].v);a[i].idi;}int x,y;for(int i2;in;i){scanf(%d,x);addline(x,i);addline(i,x);}dfs1(1,0);dfs2(1,1);//build(1,1,n);//for(int i1;in;i) printf(i%d dep%d fa%d siz%d top%d pos%d hson%d\n,i,dep[i],fa[i],siz[i],top[i],pos[i],hson[i]);//scanf(%d,m);//int op;sort(a1,a1n);for(int i1;in;i){int nowa[i].id;ans[now]ask(1,1,n,pos[now],pos[now]siz[now]-1);change(1,1,n,pos[now],1);}for(int i1;in;i) printf(%d\n,ans[i]);
}
/**/
