本文共 7604 字，大约阅读时间需要 25 分钟。

A：[NOI2014] 魔法森林

按照$a$精灵从小到大排序

按顺序插入每一条边

加入第$i$条边后的最小代价为$a[i]$加上从$1$到$n$的所有路径中最大$b$最小的路径代价

维护边权 把边在$LCT$中理解为点？——看题解代码其实就是建虚点

出现环时 选择最大的$b$删去即可

/*一些不成型的想法：贪心？？怎么贪两个呢？？——先让其中一维变成有序再着重贪另一维私以为此题这样不可做 passkruskal重构树——最小生成树最小生成树上的两点间距离最小LCT维护最小生成树a精灵从小到大排序 插入b精灵？？边权改成点权 构造虚点*/#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 150005#define inf 0x7f7f7f7f struct node {   	int u, v, a, b;}edge[maxn];struct LCT {   	int f, val, rev, id;	int son[2];}t[maxn];int n, m, ans = inf;int st[maxn], w[maxn];bool cmp( node x, node y ) {   	return ( x.a == y.a ) ? ( x.b < y.b ) : ( x.a < y.a );}bool isroot( int x ) {   	return t[t[x].f].son[0] == x || t[t[x].f].son[1] == x;}void pushup( int x ) {   	t[x].id = x, t[x].val = w[x];	if( t[x].son[0] && t[t[x].son[0]].val > t[x].val ) {   		t[x].val = t[t[x].son[0]].val;		t[x].id = t[t[x].son[0]].id;	}	if( t[x].son[1] && t[t[x].son[1]].val > t[x].val ) {   		t[x].val = t[t[x].son[1]].val;		t[x].id = t[t[x].son[1]].id;	}}void rotate( int x ) {   	int fa = t[x].f, Gfa = t[fa].f, k = t[fa].son[1] == x;	if( isroot( fa ) ) t[Gfa].son[t[Gfa].son[1] == fa] = x;	t[x].f = Gfa;	if( t[x].son[k ^ 1] ) t[t[x].son[k ^ 1]].f = fa;	t[fa].son[k] = t[x].son[k ^ 1];	t[x].son[k ^ 1] = fa;	t[fa].f = x;	pushup( fa );	pushup( x );}void pushdown( int x ) {   	if( t[x].rev ) {   		swap( t[x].son[0], t[x].son[1] );		if( t[x].son[0] ) t[t[x].son[0]].rev ^= 1;		if( t[x].son[1] ) t[t[x].son[1]].rev ^= 1;		t[x].rev = 0;	}}void splay( int x ) {   	int top = 0, y = x;	st[++ top] = y;	while( isroot( y ) ) st[++ top] = y = t[y].f;	while( top ) pushdown( st[top --] );	while( isroot( x ) ) {   		int fa = t[x].f, Gfa = t[fa].f;		if( isroot( fa ) ) 			( ( t[Gfa].son[0] == fa ) ^ ( t[fa].son[0] == x ) ) ? rotate( x ) : rotate( fa );		rotate( x );	}}void access( int x ) {   	for( int son = 0;x;son = x, x = t[x].f ) {   		splay( x );		t[x].son[1] = son;		pushup( x );	}}int FindRoot( int x ) {   	access( x );	splay( x );	while( t[x].son[0] ) {   		pushdown( x );		x = t[x].son[0];	}	return x;}void MakeRoot( int x ) {   	access( x );	splay( x );	t[x].rev ^= 1;	pushdown( x );}void link( int x, int y ) {   	MakeRoot( x );	if( FindRoot( y ) != x ) t[x].f = y;}void split( int x, int y ) {   	MakeRoot( x );	access( y );	splay( y );}bool Union( int x, int y ) {   	MakeRoot( x );	return FindRoot( y ) == x;}int main() {   	scanf( "%d %d", &n, &m );	for( int i = 1;i <= m;i ++ )		scanf( "%d %d %d %d", &edge[i].u, &edge[i].v, &edge[i].a, &edge[i].b );	sort( edge + 1, edge + m + 1, cmp );	for( int i = 1;i <= m;i ++ ) {   		w[i + n] = edge[i].b;		int u = edge[i].u, v = edge[i].v;		if( u == v ) continue;		if( Union( u, v ) ) {   			split( u, v );			if( t[v].val <= edge[i].b ) continue;			int x = t[v].id;			splay( x );			t[t[x].son[0]].f = t[t[x].son[1]].f = 0;			link( u, i + n ), link( i + n, v );		}		else			link( u, i + n ), link( i + n, v );		if( Union( 1, n ) ) split( 1, n ), ans = min( ans, edge[i].a + t[n].val );	}	if( ans == inf ) printf( "-1\n" );	else printf( "%d\n", ans );	return 0;}
     
    
   

D：[ZJOI2018]历史

一句话题意： 给出一棵树,给定每一个点的$access$次数,计算轻重链切换次数的最大值,带修改

先不考虑带修改的问题

点$u$，只有在$u$子树里的点进行$access$才会影响答案，并且点独立，可以分开算

假设$u$的子树发生了两次$access$，当且仅当这两次操作的点分属于$u$两个不同儿子的子树中，答案才会$+1$

要使答案最大，就是尽量让所有相邻发生的崛起都来自不同子树

相当于有$[0,m]$种颜色，每种颜色有$a_i$个，最大化相邻颜色不同的个数

设$tot={\sum }_{i=0}^m{a}_i,maxx=ma{x}_{i=0}^m\{$

答案则为$min\{$

考虑先放最多的$maxx$个然后插空，对于剩下的$pos=tot-maxx$个

如果$pos\le maxx-1$，显然直接插空，贡献$2\times p$个

如果$pos>maxx-1$，一定可以通过不断来回插空，达到上界$tot-1$

在$O(n)$的时间搜一遍整棵树即可

现在加上修改

根据$2\times maxx\ge tot+1$这个分界线处理

为什么这个是分界线？？当满足这个式子的时候，答案一定取后者$2\times (tot-maxx)$

令$op{t}_i$表示$i$子树的操作次数和，如果满足$2\times op{t}_i\ge op{t}_{f{a}_i}+1$，就把$i\to fa$连为实边，否则为虚边

为什么这么定义？？因为在这样的定义下，如果$i$子树内操作$j$加上权值$w$，其只会影响$j$到根路径上的点的答案和虚边关系

因为对于实边，存在$2(op{t}_i+w)\ge (op{t}_{f{a}_i}+w)+1$，即实边还是实边

并且答案$\Delta =2[(op{t}_{f{a}_i}+w)-(op{t}_i+w)]-2[op{t}_{f{a}_i}-op{t}_i]=0$ 是不变的

对于怎么找到路径上的虚边，就写$LCT$，因为这里的操作是类似于$access$的，只不过要判断一下虚实边之间的变换

$ans$减去点更新前的答案再加上更新后的答案即可

#include 
   
    #include 
    
     using namespace std;#define int long long#define maxn 400005struct node {   	int fa, val, sum, thin_edge_sum;	int son[2];}t[maxn];vector < int > G[maxn];int n, m, ans;bool isroot( int x ) {   	return t[t[x].fa].son[0] == x || t[t[x].fa].son[1] == x;}void pushup( int x ) {   	t[x].sum = t[x].val + t[t[x].son[0]].sum + t[t[x].son[1]].sum + t[x].thin_edge_sum;} void rotate( int x ) {   	int fa = t[x].fa, Gfa = t[fa].fa, k = t[fa].son[1] == x;	if( isroot( fa ) ) t[Gfa].son[t[Gfa].son[1] == fa] = x;	t[x].fa = Gfa;	if( t[x].son[k ^ 1] ) t[t[x].son[k ^ 1]].fa = fa;	t[fa].son[k] = t[x].son[k ^ 1];	t[x].son[k ^ 1] = fa;	t[fa].fa = x;	pushup( fa );	pushup( x );}void splay( int x ) {   	while( isroot( x ) ) {   		int fa = t[x].fa, Gfa = t[fa].fa;		if( isroot( fa ) )			( ( t[Gfa].son[1] == fa ) ^ ( t[fa].son[1] == x ) ) ? rotate( fa ): rotate( x );		rotate( x );	}}int calc( int x, int tot, int maxx ) {   	if( t[x].son[1] ) return ( tot - maxx ) * 2;	else if( t[x].val * 2 > tot ) return ( tot - t[x].val ) * 2;	else return tot - 1;}void modify( int x, int w ) {   	splay( x );    /*    	如果想要得到某一个点的tot    	就应该计算splay里面深度≥它的点的val之和    	也就是将这个点splay到根后    	这个点的val加上其右子树的val和    */	int tot = t[x].sum - t[t[x].son[0]].sum;	int maxx = t[t[x].son[1]].sum;	ans -= calc( x, tot, maxx );	t[x].val += w, tot += w, t[x].sum += w;	if( maxx * 2 < tot + 1 ) {    //实边变虚边		t[x].thin_edge_sum += maxx;		t[x].son[1] = 0;	}	ans += calc( x, tot, maxx );	pushup( x );	int son;	for( x = t[son = x].fa;x;x = t[son = x].fa ) {   		splay( x );		int tot = t[x].sum - t[t[x].son[0]].sum;		int maxx = t[t[x].son[1]].sum;		ans -= calc( x, tot, maxx );		t[x].thin_edge_sum += w, tot += w, t[x].sum += w;		if( maxx * 2 < tot + 1 ) {   			t[x].thin_edge_sum += maxx;			t[x].son[1] = 0;			maxx = 0;		}		if( t[son].sum * 2 > tot ) {   			t[x].thin_edge_sum -= t[son].sum;			t[x].son[1] = son;			maxx = t[son].sum;		}		ans += calc( x, tot, maxx );		pushup( x );	}}void dfs( int u ) {   	t[u].sum = t[u].val;	int pos = 0, maxx = t[u].val;	for( int i = 0;i < G[u].size();i ++ ) {   		int v = G[u][i];		if( v == t[u].fa ) continue;		t[v].fa = u;		dfs( v );		t[u].sum += t[v].sum;		if( t[v].sum > maxx ) maxx = t[v].sum, pos = v;	}	ans += min( t[u].sum - 1, ( t[u].sum - maxx ) * 2 );	if( maxx * 2 >= t[u].sum + 1 ) t[u].son[1] = pos; //实边 修改是不会更改贡献的	t[u].thin_edge_sum = t[u].sum - t[u].val - t[t[u].son[1]].sum;//所有虚边的操作数和 以后是会更改贡献的}signed main() {   	scanf( "%lld %lld", &n, &m );	for( int i = 1;i <= n;i ++ )		scanf( "%lld", &t[i].val );	for( int i = 1, u, v;i < n;i ++ ) {   		scanf( "%lld %lld", &u, &v );		G[u].push_back( v );		G[v].push_back( u );  	}	dfs( 1 );	printf( "%lld\n", ans );	for( int i = 1, x, y;i <= m;i ++ ) {   		scanf( "%lld %lld", &x, &y );		modify( x, y );		printf( "%lld\n", ans );	}	return 0;}