网站建设费用大概多少钱,网站开发实施方案进度,亚马逊雨林深处,关于政协 网站建设解析
本题需要用LCT维护子树大小 然后我就不会了 然后我就用树剖水过去了 又快又好写#xff0c;真香
现在详细聊聊如何用LCT维护子树信息 每个结点再定义一个新的变量记录所有虚儿子的信息 然后…完了#xff1f;
告别盲目pushup#xff0c;我们来详细聊聊在哪里需要更新…解析
本题需要用LCT维护子树大小 然后我就不会了 然后我就用树剖水过去了 又快又好写真香
现在详细聊聊如何用LCT维护子树信息 每个结点再定义一个新的变量记录所有虚儿子的信息 然后…完了
告别盲目pushup我们来详细聊聊在哪里需要更新虚儿子的信息
毋庸置疑应该在虚儿子信息改变的时候废话 那么什么时候发生改变呢
access虚实边会交换状态需要更新虚子树状态link增加了虚儿子需要更新虚子树状态
没了 splay、rotate、makeroot、findroot都是在一个splay里自己玩泥巴显然不会改变虚儿子的状态 注意cut是减少了一个实儿子也没有改变虚儿子状态 似乎还不太难对吧 所以对于LCT的标记问题我们要理性分析相信科学
update: 纸上得来终觉浅绝知此事要躬行 翻译不要口胡 qwq 不自己写一遍是真的找不到坑点… 这里的link改变虚子树状态的时候会连带上面一串splay的信息都出问题 而且由于其他地方默认的是原来的信息正确因此这里即使后面splay或makeroot也于事无补 解决办法是把y转到根再更新其虚子树信息
inline void link(int x,int y){makeroot(x);access(y);splay(y);siz0[y]siz[x];f[x]y;pushup(y);return;
}代码
然而懒得重写还是贴的我的树剖 明天晨练可以写遍这个
#includebits/stdc.h
using namespace std;
#define ll long long
const int N2e5100;
const int mod1e97;
const double eps1e-9;
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;
}int n,m;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}
struct ope{int op,x,y;
}q[N];
struct edge{int x,y;
}e[N];
int tot,fa[N],num[N];
int find(int x){return xfa[x]?x:find(fa[x]);}
inline void merge(int x,int y){xfind(x);yfind(y);if(num[x]num[y]) swap(x,y);e[tot](edge){x,y};fa[x]y;num[y]num[x];return;
}int dfn[N],pos[N],tim,f[N],siz[N],hson[N],top[N];
int pl[N][19];
void dfs1(int x,int fa){f[x]fa;pl[x][0]fa;for(int k1;pl[x][k-1];k) pl[x][k]pl[pl[x][k-1]][k-1];siz[x]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa) continue;dfs1(to,x);siz[x]siz[to];if(siz[to]siz[hson[x]]) hson[x]to;}return;
}
void dfs2(int x,int tp){top[x]tp;pos[x]tim;dfn[tim]x;if(hson[x]) dfs2(hson[x],tp);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof[x]||tohson[x]) continue;dfs2(to,to);}return;
}int val[N];
inline void add(int p,int w){for(;pn;pp-p) val[p]w;return;
}
inline int ask(int p){int res(0);for(;p;p-p-p) resval[p];return res;
}
void init(){for(int i1;in;i){add(pos[i],siz[i]);add(pos[i]1,-siz[i]);}return;
}void upd(int x,int anc,int w){while(top[x]!top[anc]){add(pos[top[x]],w);add(pos[x]1,-w);xf[top[x]];}add(pos[anc],w);add(pos[x]1,-w);return;
}ll ans[N];
int o;
int main() {
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();mread();for(int i1;in;i) num[i]1,fa[i]i;for(int i1;im;i){char c;int x,y;scanf( %c,c);xread(),yread();q[i](ope){cA,x,y};if(cA){addline(x,y);addline(y,x);merge(x,y);}}for(int i1;in;i){if(!siz[i]){dfs1(i,0);dfs2(i,i);}}init();for(int im;i1;i--){if(q[i].op){int xe[tot].x,ye[tot].y;--tot;num[y]-num[x];fa[x]x;xq[i].x,yq[i].y; if(f[x]y) swap(x,y);int wask(pos[y]);int tpx,oofind(x);for(int k17;k0;k--){if(!pl[tp][k]||find(pl[tp][k])!oo) continue;tppl[tp][k];}upd(x,tp,-w);//printf(cut:(%d %d) w%d tp%d\n\n,x,y,w,tp);}else{int xq[i].x,yq[i].y;if(f[x]y) swap(x,y);int sumnum[find(x)],botask(pos[y]);ans[o]1ll*bot*(sum-bot);//printf((%d %d):sum%d bot%d\n\n,x,y,sum,bot);}}while(o) printf(%lld\n,ans[o--]);return 0;
}
/*
8 12
A 2 3
Q 2 3
A 3 4
Q 2 3
A 3 8
Q 3 8
Q 3 4
Q 2 3
A 8 7
A 6 5
Q 8 7
Q 5 6*/
