首先题目要我们求的是叶子节点的前序遍历\((\)逆序对数\()\)最小值。
不难想到一个性质，一个点的子树内部的答案不会因为交换左右子树而改变。
所以我们可以贪心 \(->\) 对于每个点的子树都弄出最优(逆序对)。
所以实际上我们要求的是：
\(1.\)左-右的答案。
\(2.\)右-左的答案。
较为暴力的想法去求答案就是：(以求左-右为例)
如果要合并某一点的左右子树答案，我们就需要得知权值。
可以对每个点开一颗权值线段树，那么如果我需要得知某一个点的左-右答案怎么来呢？我们可以暴力的去查找每一个权值。假设其为\(x\)
那么左-右在x处产生的答案就是：
左子树：\((1-x)*\) 右子树：\((x-n)\)的数量。
然后我们可以在权值线段树内递归的处理每一个\(x\)，同时合并所有的权值。
这貌似就是线段树合并\(QAQ()\)然而良心出题人让我们不得不把某一个点的右子树合并到左子树里面去\((\)否则空间开销难以接受\(QAQ)\)
每次贪心取其中一种答案加上就好了
#include<bits/stdc++.h>
using namespace std;
int read() {
char cc = getchar(); int cn = 0, flus = 1;
while(cc < '0' || cc > '9') { if( cc == '-' ) flus = -flus; cc = getchar(); }
while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar();
return cn * flus;
}
const int N = 400000 + 5;
#define LL long long
#define ls(x) tr[x].l
#define rs(x) tr[x].r
struct Tr{
int val, l, r;
}tr[N * 25];
int maxv, n, cot, cnt, root[N];
LL Ans, ans1, ans2;
void update( int &x, int l, int r, int wh ) {
if( !x ) x = ++ cot;
++ tr[x].val;
if( l == r ) return ;
int mid = ( l + r ) >> 1;
if( mid >= wh ) update( ls(x), l, mid, wh );
else update( rs(x), mid + 1, r, wh );
}
void merge( int &lx, int rx ) {
if( !lx || !rx ) { lx = lx + rx; return ; }
tr[lx].val = tr[lx].val + tr[rx].val;
ans1 += 1ll * tr[tr[lx].r].val * tr[tr[rx].l].val;
ans2 += 1ll * tr[tr[rx].r].val * tr[tr[lx].l].val;
merge( tr[lx].l, tr[rx].l );
merge( tr[lx].r, tr[rx].r );
}
void dfs( int &x ) {
int t, ls, rs;
t = read();
if( t != 0 ) {
x = ++ cnt, update( root[x], 1, n, t );
return ;
}
dfs( ls ), dfs( rs ), ans1 = ans2 = 0, x = ls;
merge( root[x], root[rs] );
Ans += min( ans1, ans2 );
}
signed main()
{
n = read();
dfs(root[0]);
printf("%lld\n", Ans );
return 0;
}
比较朴素的想法：树上差分+权值线段树合并
这道题给了一点点小小的注意：
\((1):\)注意权值线段树的范围\(QWQ\)
\((2):\)合并的时候注意优先级。
记录一点点思路，当时 \(55\) 分的代码是这样的：
void merge( int &lx, int rx, int l, int r ) {
if( l == r ) { tr[lx].mx += tr[rx].mx; return ; }
if( !lx || !rx ) { lx = lx + rx; return ; }
int mid = ( l + r ) >> 1;
merge( ls(lx), ls(rx), l, mid ), merge( rs(lx), rs(rx), mid + 1, r );
tr[lx].mx = max( tr[ls(lx)].mx, tr[rs(lx)].mx );
}
后来的 \(100\) 分代码是这样：
void merge( int &lx, int rx, int l, int r ) {
if( !lx || !rx ) { lx = lx + rx; return ; }
if( l == r ) { tr[lx].mx += tr[rx].mx; return ; }
int mid = ( l + r ) >> 1;
merge( ls(lx), ls(rx), l, mid ), merge( rs(lx), rs(rx), mid + 1, r );
tr[lx].mx = max( tr[ls(lx)].mx, tr[rs(lx)].mx );
}
注意要先判断点是否存在再合并，不然可能会合并到 \(0\) (空)节点处。
以及给自己的一点小想法？
用权值线段树查出现次数最多的数可以通过不断的比对左右儿子的\(max\)来二分找。
代码：
#include<bits/stdc++.h>
using namespace std;
int read() {
char cc = getchar(); int cn = 0, flus = 1;
while(cc < '0' || cc > '9') { if( cc == '-' ) flus = -flus; cc = getchar(); }
while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar();
return cn * flus;
}
const int N = 200000 + 5;
#define ls(x) tr[x].l
#define rs(x) tr[x].r
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define drep( i, t, s ) for( register int i = t; i >= s; -- i )
struct E {
int to, next;
}e[N * 2];
struct Tree {
int l, r, mx;
}tr[N * 25];
int fath[N][20], n, m, head[N], root[N], dep[N], cnt, num, Maxc, ans[N];
void add( int x, int y ) {
e[++ cnt] = (E){ y, head[x] }, head[x] = cnt;
e[++ cnt] = (E){ x, head[y] }, head[y] = cnt;
}
void dfs( int x, int fa ) {
fath[x][0] = fa, dep[x] = dep[fa] + 1;
rep( i, 1, 19 ) fath[x][i] = fath[fath[x][i - 1]][i - 1];
Next( i, x ) {
int v = e[i].to;
if( v == fa ) continue;
dfs( v, x );
}
}
int LCA( int x, int y ) {
if( dep[x] < dep[y] ) swap( x, y );
drep( i, 19, 0 ) if( dep[fath[x][i]] >= dep[y] ) x = fath[x][i];
drep( i, 19, 0 ) if( fath[x][i] != fath[y][i] ) x = fath[x][i], y = fath[y][i];
return ( x == y ) ? x : fath[x][0];
}
void update( int &x, int ll, int rr, int wh, int add ) {
if( !x ) x = ++ num ;
if( ll == rr ) { tr[x].mx += add; return ; }
int mid = ( ll + rr ) >> 1;
if( mid >= wh ) update( ls(x), ll, mid, wh, add );
else update( rs(x), mid + 1, rr, wh, add );
tr[x].mx = max( tr[ls(x)].mx, tr[rs(x)].mx );
}
void merge( int &lx, int rx, int l, int r ) {
if( !lx || !rx ) { lx = lx + rx; return ; }
if( l == r ) { tr[lx].mx += tr[rx].mx; return ; }
int mid = ( l + r ) >> 1;
merge( ls(lx), ls(rx), l, mid ), merge( rs(lx), rs(rx), mid + 1, r );
tr[lx].mx = max( tr[ls(lx)].mx, tr[rs(lx)].mx );
}
int query_Mx( int x, int l, int r ) {
int mid = ( l + r ) >> 1;
if( !tr[x].mx ) return 0;
while( l != r ) {
mid = ( l + r ) >> 1;
if( tr[ls(x)].mx >= tr[rs(x)].mx ) r = mid, x = ls(x);
else l = mid + 1, x = rs(x);
}
return l;
}
void solve( int x, int y, int z ) {
int lca = LCA( x, y );
update( root[lca], 1, Maxc, z, -1 );
if( fath[lca][0] ) update( root[fath[lca][0]], 1, Maxc, z, -1 );
update( root[x], 1, Maxc, z, 1 );
update( root[y], 1, Maxc, z, 1 );
}
void dfs_merge( int x, int fa ) {
Next( i, x ) {
int v = e[i].to;
if( v == fa ) continue;
dfs_merge( v, x );
merge( root[x], root[v], 1, Maxc );
}
ans[x] = query_Mx( root[x], 1, Maxc );
}
signed main()
{
n = read(), m = read();
int x, y, z; Maxc = 100000;
rep( i, 1, n - 1 ) x = read(), y = read(), add( x, y );
dfs( 1, 0 );
rep( i, 1, m ) x = read(), y = read(), z = read(), solve( x, y, z ) ;
dfs_merge( 1, 0 );
rep( i, 1, n ) printf("%d\n", ans[i] );
return 0;
}