网站运维工作内容拉新充场app推广平台

http://cplusoj.com/d/senior/p/SS231025D

答案为 $\sum w[x]-w[son[x]]$，$x$ 非儿子

要维护断边，LCT固然可以，但不一定需要

发现如果发生了变化，只会由重儿子变成次重儿子

所以我们首先要维护次重儿子

同时我们拿树状数组维护其所有祖先的重儿子与次重儿子之差。

此时我们只需要在树状数组对应位置进行查询即可

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}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; 
vector<node>G[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(x<=n) cnt[x]+=y, x+=x&-x; }int que(int x) {int ans=0; while(x) ans+=cnt[x], x-=x&-x; return ans+cnt[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]) totans+=w[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+(p+1-B1.que(w[y]))*w[y]; if(!nxt[x]) --ans[id]; 
//			if(id==4) 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+1-B1.que(w[y]))*w[y]); dfs2(y, x, dep+1, p+1); 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(id==2) 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, dep+1, 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);
//	T=read();
//	while(T--) {
//
//	}n=read(); for(i=1; i<n; ++i) {u=read(); v=read(); if(i==1) su=u, sv=v; G[u].pb({v, i}); G[v].pb({u, i}); }Bin.sex=1; dfs1(su, sv); dfs1(sv, su); totans+=n-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); flg=1; }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); flg=0; }//	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); flg=1; }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); flg=0; }for(i=2; i<n; ++i) printf("%d\n", ans[i]); return 0;
}