网站seo优化关键词,申请关闭网站,开发wordpress主题,有前景的网站建设http://cplusoj.com/d/senior/p/SS231025D
答案为 ∑ w [ x ] − w [ s o n [ x ] ] \sum w[x]-w[son[x]] ∑w[x]−w[son[x]]#xff0c; x x x 非儿子 要维护断边#xff0c;LCT固然可以#xff0c;但不一定需要
发现如果发生了变化#xff0c;只会由重儿子变成次重儿子…http://cplusoj.com/d/senior/p/SS231025D
答案为 ∑ w [ x ] − w [ s o n [ x ] ] \sum w[x]-w[son[x]] ∑w[x]−w[son[x]] x x x 非儿子 要维护断边LCT固然可以但不一定需要
发现如果发生了变化只会由重儿子变成次重儿子
所以我们首先要维护次重儿子
同时我们拿树状数组维护其所有祖先的重儿子与次重儿子之差。
此时我们只需要在树状数组对应位置进行查询即可
#includebits/stdc.h
using namespace std;
//#define int long long
inline int read(){int x0,f1;char chgetchar(); while(ch0||
ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){
x(x1)(x3)(ch^48);chgetchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 500010
//#define M
//#define mo
struct node {int y, id;
};
int n, m, i, j, k, T;
int ans[N], w[N], nxt[N], totans, son[N], sum[N];
int u, v, su, sv, flg;
vectornodeG[N]; struct Binary_tree {int cnt[N], sex; void add(int x, int y) {
// if(sex) printf(Add %d : %d\n, x, y); if(!x) {cnt[0]y; return; }while(xn) cnt[x]y, xx-x; }int que(int x) {int ans0; while(x) anscnt[x], x-x-x; return anscnt[0]; }
}Bin, B1;void dfs1(int x, int fa) {w[x]1;for(auto t : G[x]) {int y t.y; if(y fa) continue; dfs1(y, x); w[x]w[y]; sum[x]sum[y]; if(w[y]w[son[x]]) nxt[x]son[x], son[x]y; else if(w[y]w[nxt[x]]) nxt[x]y; }if(son[x]) totansw[x]-w[son[x]], sum[x]w[x]-w[son[x]];
// printf(sum[%lld] %lld || %lld %lld || %d\n, x, sum[x], son[x], nxt[x], w[x]);
}void dfs2(int x, int fa, int dep, int p) {for(auto t : G[x]) {int y t.y, id t.id; if(y fa) continue;
// printf(%d-%d\n, x, y);
// dfs2(y, x); if(y son[x]) {Bin.add(w[son[x]]-w[nxt[x]], w[son[x]]-w[nxt[x]]); B1.add(w[son[x]]-w[nxt[x]], 1); ans[id]totans-sum[y]Bin.que(w[y])-w[y]*dep(p1-B1.que(w[y]))*w[y]; if(!nxt[x]) --ans[id];
// if(id4) printf(%d(totans) %d(-sum[y]) %d(_change_son) %d(-size) %d(son)\n,
// totans, sum[y], Bin.que(w[y]), w[y]*dep, (p1-B1.que(w[y]))*w[y]); dfs2(y, x, dep1, p1); Bin.add(w[son[x]]-w[nxt[x]], -(w[son[x]]-w[nxt[x]])); B1.add(w[son[x]]-w[nxt[x]], -1); }else {
// if(id2) printf(%d(totans) %d(-sum[y]) %d(_change_son) %d(-size) %d(son)\n,
// totans, sum[y], Bin.que(w[y]), w[y]*dep, (p-B1.que(w[y]))*w[y]); ans[id]totans-sum[y]Bin.que(w[y])-w[y]*dep(p-B1.que(w[y]))*w[y];
// B1.add(w[son[x]]-w[nxt[x]], 1); dfs2(y, x, dep1, p);
// B1.add(w[son[x]]-w[nxt[x]], -1); }}
}signed main()
{
// freopen(in.txt, r, stdin);
// freopen(out.txt, w, stdout);freopen(tree.in, r, stdin);freopen(tree.out, w, stdout);
// Tread();
// while(T--) {
//
// }nread(); for(i1; in; i) {uread(); vread(); if(i1) suu, svv; G[u].pb({v, i}); G[v].pb({u, i}); }Bin.sex1; dfs1(su, sv); dfs1(sv, su); totansn-max(w[su], w[sv])-1;
// printf( %d\n, totans); if(w[su]w[sv]) {Bin.add(w[su]-w[sv], w[su]-w[sv]); B1.add(w[su]-w[sv], 1); flg1; }dfs2(su, sv, 2, flg);if(w[su]w[sv]) {Bin.add(w[su]-w[sv], -(w[su]-w[sv])); B1.add(w[su]-w[sv], -1); flg0; }// printf(# %lld\n, sv); if(w[sv]w[su]) {Bin.add(w[sv]-w[su], (w[sv]-w[su])); B1.add(w[sv]-w[su], 1); flg1; }dfs2(sv, su, 2, flg);if(w[sv]w[su]) {Bin.add(w[sv]-w[su], -(w[sv]-w[su])); B1.add(w[sv]-w[su], -1); flg0; }for(i2; in; i) printf(%d\n, ans[i]); return 0;
}
