海阳市城建设局网站,新手做网站免费域名,wordpress如何安装模板文件,电影网站开发[NOI2014] 魔法森林
题目
按照aaa精灵从小到大排序
按顺序插入每一条边
加入第iii条边后的最小代价为a[i]a[i]a[i]加上从111到nnn的所有路径中最大bbb最小的路径代价
维护边权 把边在LCTLCTLCT中理解为点#xff1f;——看题解代码其实就是建虚点
出现环时 选择最大的bb…[NOI2014] 魔法森林
题目
按照aaa精灵从小到大排序
按顺序插入每一条边
加入第iii条边后的最小代价为a[i]a[i]a[i]加上从111到nnn的所有路径中最大bbb最小的路径代价
维护边权 把边在LCTLCTLCT中理解为点——看题解代码其实就是建虚点
出现环时 选择最大的bbb删去即可
/*
一些不成型的想法贪心怎么贪两个呢——先让其中一维变成有序再着重贪另一维
私以为此题这样不可做 passkruskal重构树——最小生成树
最小生成树上的两点间距离最小LCT维护最小生成树
a精灵从小到大排序 插入b精灵边权改成点权 构造虚点
*/
#include cstdio
#include iostream
#include algorithm
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 );}elselink( 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;
}[ZJOI2018]历史
题目
一句话题意 给出一棵树,给定每一个点的accessaccessaccess次数,计算轻重链切换次数的最大值,带修改
先不考虑带修改的问题
点uuu只有在uuu子树里的点进行accessaccessaccess才会影响答案并且点独立可以分开算
假设uuu的子树发生了两次accessaccessaccess当且仅当这两次操作的点分属于uuu两个不同儿子的子树中答案才会111
要使答案最大就是尽量让所有相邻发生的崛起都来自不同子树
相当于有[0,m][0,m][0,m]种颜色每种颜色有aia_iai个最大化相邻颜色不同的个数
设tot∑i0mai,maxxmaxi0m{ai}tot\sum_{i0}^ma_i,maxxmax_{i0}^m\{a_i\}tot∑i0mai,maxxmaxi0m{ai}
答案则为min{t−1,2×(tot−maxx)}min\{t-1,2\times (tot-maxx)\}min{t−1,2×(tot−maxx)}
考虑先放最多的maxxmaxxmaxx个然后插空对于剩下的postot−maxxpostot-maxxpostot−maxx个
如果pos≤maxx−1pos\le maxx-1pos≤maxx−1显然直接插空贡献2×p2\times p2×p个
如果posmaxx−1posmaxx-1posmaxx−1一定可以通过不断来回插空达到上界tot−1tot-1tot−1
在O(n)O(n)O(n)的时间搜一遍整棵树即可
现在加上修改
根据2×maxx≥tot12\times maxx\ge tot12×maxx≥tot1这个分界线处理
为什么这个是分界线当满足这个式子的时候答案一定取后者2×(tot−maxx)2\times (tot-maxx)2×(tot−maxx)
令optiopt_iopti表示iii子树的操作次数和如果满足2×opti≥optfai12\times opt_i\ge opt_{fa_i}12×opti≥optfai1就把i→fai\rightarrow fai→fa连为实边否则为虚边
为什么这么定义因为在这样的定义下如果iii子树内操作jjj加上权值www其只会影响jjj到根路径上的点的答案和虚边关系
因为对于实边存在2(optiw)≥(optfaiw)12(opt_iw)\ge (opt_{fa_i}w)12(optiw)≥(optfaiw)1即实边还是实边
并且答案Δ2[(optfaiw)−(optiw)]−2[optfai−opti]0\Delta 2[(opt_{fa_i}w)-(opt_iw)]-2[opt_{fa_i}-opt_i]0Δ2[(optfaiw)−(optiw)]−2[optfai−opti]0 是不变的
对于怎么找到路径上的虚边就写LCTLCTLCT因为这里的操作是类似于accessaccessaccess的只不过要判断一下虚实边之间的变换
ansansans减去点更新前的答案再加上更新后的答案即可
#include cstdio
#include vector
using namespace std;
#define int long long
#define maxn 400005
struct 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;
}
