树上形态改变统计贡献：1025T4

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

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

---

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

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

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

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

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

#include
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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130