wordpress站酷首页,谷歌优化,网站后台邮箱设置,设计说明ai生成前言
有点懊恼的一个题… 并没有其他那些ZJOI那么毒瘤#xff0c;看出了关键结论#xff0c;但最后维护卡在log条虚边的伞兵性质上了。
解析
第一眼#xff1a;感觉根本不可做啊。 冷静一下#xff0c;既然它还变态的带修#xff0c;一定是可以转化成比较形式化的东西的…前言
有点懊恼的一个题… 并没有其他那些ZJOI那么毒瘤看出了关键结论但最后维护卡在log条虚边的伞兵性质上了。
解析
第一眼感觉根本不可做啊。 冷静一下既然它还变态的带修一定是可以转化成比较形式化的东西的。 对每个节点考虑对答案贡献了多少次设 sxs_xsx 表示 x 子树内权值之和mxxmx_xmxx 表示 max(ax,maxu∈sonxsu)\max(a_x,\max_{u\in son_{x}}s_{u})max(ax,maxu∈sonxsu)那么答案的上界显然是 sx−1s_x-1sx−1但前提是不同子树的权值必须交错出现因此其实应该是 min(sx−1,2(sx−mxx))\min(s_x-1,2(s_x-mx_x))min(sx−1,2(sx−mxx))递归的想可以发现这个结论一直都是对的。写一发暴力得到了30分说明结论没有问题。
考虑如何快速的维护修改。 一个节点 x 收到某个儿子 son “一家独大”的制约当且仅当 2∗sson≥sx12*s_{son}\ge s_x12∗sson≥sx1。显然至多存在一个这样的儿子定义其为 hsonxhson_xhsonx特别的hsonxhson_xhsonx 可以为 x 自己(x,hsonx)(x,hson_x)(x,hsonx) 这样的边定义为实边其他边定义为虚边。 考虑对一个节点 x w贡献发生改变的必然是一条返祖链。进一步发现对于返祖链上的一条实边其父亲端的贡献必然不会改变。 然后我觉的虚实边变来变去我就不会了。
接下来通过和树剖类似的证明 可以得出任意一条返祖链上的虚边最多有 logai\log a_ilogai 条。 所以暴力跳修改所有虚边的贡献即可。 实现上树剖后开两棵线段树一棵维护虚实边一棵维护 sxs_xsx 即可。 时间复杂度 O(nlogn(lognlog∑ai))O(n\log n(\log n\log {\sum a_i}))O(nlogn(lognlog∑ai))。
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N4e5100;
const int mod1e97;bool mem1;inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;struct seg{
#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)ll sum[N2],laz[N2];inline void pushup(int k){sum[k]sum[ls]sum[rs];}inline void add(int k,int l,int r,ll w){sum[k](r-l1)*w;laz[k]w;}inline void pushdown(int k,int l,int r){ll olaz[k];laz[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 y,ll w){if(xlry){add(k,l,r,w);return;}pushdown(k,l,r);if(xmid) change(ls,l,mid,x,y,w);if(ymid) change(rs,mid1,r,x,y,w);pushup(k);}int findpre(int k,int l,int r,int p){if(!k) exit(0);//debug(k%d (%d %d) p%d\n,k,l,r,p);if(!sum[k]) return 0;if(lr) return l;if(pmid) return findpre(ls,l,mid,p);pushdown(k,l,r);int ofindpre(rs,mid1,r,p);if(o) return o;else return findpre(ls,l,mid,p);}ll ask(int k,int l,int r,int p){if(lr) return sum[k];pushdown(k,l,r);if(pmid) return ask(ls,l,mid,p);else return ask(rs,mid1,r,p);}
}t1,t2;
//t1:s
//t2:tagll a[N],s[N],mx[N],ans;
int hson[N],siz[N],top[N],dep[N],fa[N],dfn[N],pos[N],tim;
bool tag[N];
vectorinte[N];
void dfs1(int x,int f){siz[x]1;dep[x]dep[f]1;fa[x]f;s[x]mx[x]a[x];hson[x]x;for(int to:e[x]){if(tof) continue;dfs1(to,x);siz[x]siz[to];s[x]s[to];if(s[to]mx[x]){hson[x]to;mx[x]s[to];}}ansmin(s[x]-1,2*(s[x]-mx[x]));ll shhson[x]x?a[x]:s[hson[x]];if(2*shs[x]1) hson[x]0;if(hson[x]hson[x]!x) tag[hson[x]]1;return;
}
void dfs2(int x,int tp){//debug(x%d tp%d\n,x,tp);top[x]tp;dfn[tim]x;pos[x]tim;int son0;for(int to:e[x]){if(tofa[x]) continue;if(siz[to]siz[son]) sonto;}if(son) dfs2(son,tp);for(int to:e[x]){if(tofa[x]||toson) continue;dfs2(to,to);}return;
}
void init(){ dfs1(1,0);dfs2(1,1);for(int i1;in;i){t1.change(1,1,n,pos[i],pos[i],s[i]);if(i1!tag[i]) t2.change(1,1,n,pos[i],pos[i],1);//printf(i%d hson%d s%lld tag%d\n,i,hson[i],s[i],tag[i]);}return;
}
inline ll calc(ll s,ll mx){return min(s-1,2*(s-mx));
}inline void upd(int x,int w){int orix;//printf(upd: x%d w%d\n,x,w);if(hson[x]!x){int sonhson[x];ll shson?t1.ask(1,1,n,pos[son]):0,sxt1.ask(1,1,n,pos[x]); ans-calc(sx,sh);anscalc(sxw,max(sh,a[x]w));//printf( x%d son%d sh%lld ans%lld\n,x,son,sh,ans);if(son2*sh(sxw)1){t2.change(1,1,n,pos[son],pos[son],1);hson[x]0;}if(2*(a[x]w)(sxw)1){hson[x]x;}}while(x){int pt2.findpre(1,1,n,pos[x]);if(p0||ppos[top[x]]) xfa[top[x]];else{xdfn[p];int sonhson[fa[x]];ll sft1.ask(1,1,n,pos[fa[x]]),shson?sonfa[x]?a[fa[x]]:t1.ask(1,1,n,pos[son]):0,sxt1.ask(1,1,n,pos[x]); ans-calc(sf,sh);anscalc(sfw,max(sxw,sh));//printf( x%d son%d sf%lld sh%lld sx%lld p%d ans%lld\n,x,son,sf,sh,sx,p,ans);if(son2*sh(sfw)1){t2.change(1,1,n,pos[son],pos[son],1);hson[fa[x]]0;}if(2*(sxw)(sfw)1){t2.change(1,1,n,pos[x],pos[x],-1);hson[fa[x]]x;}xfa[x];}}xori;a[x]w;while(x){t1.change(1,1,n,pos[top[x]],pos[x],w);xfa[top[x]];}return;
}bool mem2;
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();mread();for(int i1;in;i) a[i]read();for(int i1;in;i){int xread(),yread();e[x].push_back(y);e[y].push_back(x);}init();printf(%lld\n,ans);for(int i1;im;i){int xread(),wread();upd(x,w);printf(%lld\n,ans);}return 0;
}
/*
*/
