房产网站制作流程,推广网,做网站代理能赚钱吗,烟台seo推广优化传送门
首先#xff0c;在结点uuu放上w[u]w[u]w[u]个石子后#xff0c;出于贪心考虑#xff0c;下一步一定会把uuu的所有儿子vvv上的石子收回手中。
转换题意#xff1a; 记cntcntcnt为当下树上的石子数#xff0c;对每个结点uuu可以执行一次操作#xff1a;
step1. c…传送门
首先在结点uuu放上w[u]w[u]w[u]个石子后出于贪心考虑下一步一定会把uuu的所有儿子vvv上的石子收回手中。
转换题意 记cntcntcnt为当下树上的石子数对每个结点uuu可以执行一次操作
step1. cntw[u]cntw[u]cntw[u]step2. cnt−∑v∈son(u)w[v]cnt-\sum_{v\in son(u)}w[v]cnt−∑v∈son(u)w[v]
当且仅当对uuu的所有儿子vvv都执行过操作才能对uuu执行操作。 问历史上cntcntcnt的最大值最小可以是多少
先不考虑 儿子都操作完父亲才能操作的限制思考一个简单版问题有nnn个操作(a[i],b[i])(a[i],b[i])(a[i],b[i])其含义为先令cnta[i]cnta[i]cnta[i]再令cntb[i]cntb[i]cntb[i]。对这nnn个操作排序使历史上cntcntcnt的最大值最小。a[i]w[i],b[i]−∑w[v]a[i]w[i],b[i]-\sum w[v]a[i]w[i],b[i]−∑w[v]
对于一段操作i,i1,...,ji,i1,...,ji,i1,...,j设经过这段操作后cntcntdeltacntcntdeltacntcntdelta且执行这段操作途中历史上cntcntcnt的最大值为cntmxcntmxcntmx
那么每次向后添加一个二元组(a[j1]w[j1],b[j1]−∑w[v])(a[j1]w[j1],b[j1]-\sum w[v])(a[j1]w[j1],b[j1]−∑w[v]) 就相当于delta←deltaw[j1]−∑w[v],mx←max(mx,mxw[j1])delta\leftarrow deltaw[j1]-\sum w[v],mx\leftarrow max(mx,mxw[j1])delta←deltaw[j1]−∑w[v],mx←max(mx,mxw[j1])
所以我们换一种方式用二元组(w[i]−∑w[v],w[i])(w[i]-\sum w[v],w[i])(w[i]−∑w[v],w[i])来描述操作iii。 相当于操作段iii的(delta,mx)(delta,mx)(delta,mx)
由上面可以发现这个二元组是可以简易复合的。我们的问题就是给这些二元组安排一个优先级使得从左到右复合之后mxmxmx最小。
可以证明对于二元组A,BA,BA,B定义 为复合操作AAA的优先级比BBB高当且仅当(AB).max(BA).max(AB).max(BA).max(AB).max(BA).max且这样保证不存在二元组A,B,CA,B,CA,B,C满足 AB,BC,CAAB,BC,CAAB,BC,CA 。证明需要进行分类讨论
因为复合顺序改变deltadeltadelta不变所以只需考虑复合后的mxmxmx显然mxmxmx 越小越好
对于deltadeltadelta为负的二元组一定比deltadeltadelta为正的二元组优。对于deltadeltadelta都为负的二元组mxmxmx越小的优先级越高。对于deltadeltadelta都为正的二元组delta−mxdelta−mxdelta−mx越小的优先级越高。
然后我们就证明了不存在二元组A,B,CA,B,CA,B,C满足AB,BC,CAAB,BC,CAAB,BC,CA即可以按照这个优先级给二元组排序且这样最小化最终的mxmxmx 。 这样就解决了简化问题。
考虑原问题。 对uuu的所有儿子vvv都执行过操作才能对uuu执行操作 这个限制非常麻烦考虑反转 对每个点uuu可以执行一次操作
step1. 把∑v∈son(u)w[v]\sum_{v\in son(u)}w[v]∑v∈son(u)w[v]接到序列ccc的最后面step2. 把−w[u]-w[u]−w[u]接到序列ccc的最后面
对uuu的父亲fff执行过操作才能对uuu执行操作。 问序列ccc后缀和的最大值最小可以是多少。 反转前相当于每个操作先把w[u]w[u]w[u]接到ccc的最后面再把−∑w[v]-\sum w[v]−∑w[v]接到ccc的最后面求最终的ccc序列的前缀和的最大值最小可以是多少
转化后uuu点的操作对应的二元组为(∑w[v]−w[u],∑w[v])(\sum w[v]-w[u],\sum w[v])(∑w[v]−w[u],∑w[v])
观察发现任意两个二元组合并以后优先级至少比之前的一个二元组优先级低所以对于某一时刻优先级最高的二元组就算其父亲还没有放其也会在其父亲被放之后马上被放所以可以直接将这个二元组与它的父亲合并。那么用一个堆维护一下当前优先级最高的二元组就得到了根的答案的操作序列。
最后有一个结论对于任意一个节点其答案的操作序列一定是根的操作序列的一个子序列这里不太需要证明直接从优先级的角度考虑就好了所以用线段树合并维护每一个子树里的操作序列和结合后的答案即可总复杂度 O(nlogn)O(nlogn)O(nlogn)。
#includeiostream
#includecstdio
#includevector
#includeset
using namespace std;
typedef long long ll;
const int inf0x3f3f3f3f;
const int N2e510;
int T,n,par[N],fa[N];
int vis[N],b[N],c[N],tim;
int rt[N];
ll w[N],sw[N],ans[N];
vectorint g[N],vec[N];
struct Node{ll delta,mx;int id;friend Node operator (Node a,Node b){return (Node){a.deltab.delta,max(a.mx,a.deltab.mx),a.id};}friend bool operator (Node a,Node b){ll tmp1max(a.mx,a.deltab.mx);ll tmp2max(b.mx,b.deltaa.mx);if(tmp1!tmp2) return tmp1tmp2;if(a.delta!b.delta) return a.deltab.delta;if(a.mx!b.mx) return a.mxb.mx;return a.idb.id;}
}a[N];
setNode s;
int find(int x){if(xfa[x]) return x;return fa[x]find(fa[x]);
}
void init(int x){vis[x]1;b[x]tim;c[tim]x;for(int i0;ivec[x].size();i) init(vec[x][i]);
}
namespace Seg{int ls[N*30],rs[N*30],tot;Node tr[N*30];void pushup(int u){if(!ls[u]){tr[u]tr[rs[u]];return;}if(!rs[u]){tr[u]tr[ls[u]];return;}tr[u]tr[ls[u]]tr[rs[u]];}void insert(int u,int l,int r,int pos){if(!u) utot;if(lr){tr[u]a[l];return;}int mid(lr)1;if(posmid) insert(ls[u],l,mid,pos);else insert(rs[u],mid1,r,pos);pushup(u);}int merge(int x,int y){if(!x||!y) return xy;ls[x]merge(ls[x],ls[y]);rs[x]merge(rs[x],rs[y]);pushup(x);return x;}
}
void dfs(int u){Seg::insert(rt[u],1,n,b[u]);for(int i0;ig[u].size();i){int vg[u][i];dfs(v);rt[u]Seg::merge(rt[u],rt[v]);}ans[u]Seg::tr[rt[u]].mx;
}
int main(){scanf(%d,T);scanf(%d,n);for(int i2;in;i){scanf(%d,par[i]);g[par[i]].push_back(i);}for(int i1;in;i){scanf(%lld,w[i]);sw[par[i]]w[i];fa[i]i;}for(int i1;in;i){a[i](Node){sw[i]-w[i],sw[i],i};s.insert(a[i]);}for(int i1;in;i){Node now*(s.begin()); s.erase(s.begin());int xnow.id;if(x1||vis[par[x]]) init(x);else{int fxfind(par[x]);s.erase(a[fx]);a[fx]a[fx]a[x];s.insert(a[fx]);vec[fx].push_back(x),fa[x]fx;}}for(int i1;in;i){a[b[i]](Node){sw[i]-w[i],sw[i],i};}dfs(1);for(int i1;in;i)printf(%lld ,max(w[i],ans[i]w[i]));return 0;
}参考文章 https://www.cnblogs.com/mangoyang/p/11735219.html
