T1 線段樹合并&dsu on tree

Problem A: 不能說的秘密(secret)

【題目描述】

碎片散落在了一棵有 \(n\) 個頂點的有根樹上。頂點從 \(1\) 到 \(n\) 編號，頂點 \(1\) 是根，頂點 \(i\)(\(2 \le i \le n\)) 的父親編號為 \(p_i\)，其中 \(1 \le p_i < i\)。每個頂點上恰有一個碎片，頂點 \(i\) 上的碎片會在第 \(t_i\) 秒末消失。

你試著撿起頂點 \(k\) 子樹內的所有碎片。在每一秒，你可以什么也不做，也可以選擇一個滿足以下條件之一的頂點 \(i\) 并撿起頂點 \(i\) 上的碎片：

• \(i = k\)；
• 頂點 \(p_i\) 上的碎片已經被撿起。

每個碎片被撿起的時間都要在其消失之前。例如，對于一個在第 \(3\) 秒末消失的碎片，你需要在第 \(1\) 秒、第 \(2\) 秒或第 \(3\) 秒撿起它。

我們保證了 \(t_i ≥ n\)，不難發現你可以隨便撿，但是你想拖延時間。試求最遲在第多少秒初開始撿碎片能保證撿完頂點 \(k\) 子樹內的所有碎片。

你需要對于 \(k = 1, 2,...,n\) 分別求出答案。

【輸入格式】

從文件 secret.in 中讀入數據。

輸入的第一行包含一個整數 \(n\)，表示樹的頂點數量。

輸入的第二行包含 \(n-1\) 個整數，第 \(i-1\) 個整數 \(p_i\) 表示頂點 \(i\) 的父親編號。

輸入的第三行包含 \(n\) 個整數，第 \(i\) 個整數 \(t-i\) 表示頂點 \(i\) 上的碎片消失時間。

【輸出格式】

輸出到文件 secret.out 中。

輸出一行包含 \(n\) 個整數，第 \(i\) 個整數表示當 \(k = i\) 時的答案。

【樣例 1 輸入】

6
1 1 2 2 3
6 8 6 7 9 9

1 輸出】

4 6 6 7 9 9

線段樹合并和啟發式合并好題

先說思路，容易發現先按時間排序，然后從小到大依次與根節點打通最優，考慮交換處理順序，發現肯定會將最小時間提前

我們先處理好操作順序，按上述描述模擬即可，先處理根為1的

$ans=\min_{i=1}^{n}{t_i-k_i+1} $ , \(k_i\)為操作次序

那我們在每個子樹內維護即可

線段樹合并

這個處理方法真的很妙，容易發現全局操作次序的相對次序在子樹內同樣適用，假定線段樹底層是操作次序\(k_i\)，那么子樹內\(k_i\)即為線段樹底層節點前面有幾個不為空的位置+1

我們考慮線段樹合并，容易發現siz是好維護的，再維護一個ans

考慮合并，可以直接繼承左子樹答案，因為右邊已經無值，右子樹則需處理，理由如上

\(ans=min(ans_l,ans_r-siz_l)\)

普通線段樹合并即可

int insert(int p,int l,int r) {
	int id=++cnt;
	siz[id]++,val[id]=p;
	if(l==r)return id;
	int mid=l+r>>1;
	if(p<=mid) ls[id]=insert(p,l,mid);
	else rs[id]=insert(p,mid+1,r);
	return id;
}

void push_up(int p) {
	siz[p]=siz[ls[p]]+siz[rs[p]];
	val[p]=min(val[ls[p]],val[rs[p]]-siz[ls[p]]);
}
int merge(int x,int y,int l,int r) {
	if(!x||!y) return x+y;
	if(l==r) {
		siz[x]+=siz[y],val[x]=l-siz[x]+1;
		return x;
	}
	int mid=l+r>>1;
	ls[x]=merge(ls[x],ls[y],l,mid);
	rs[x]=merge(rs[x],rs[y],mid+1,r);
	push_up(x);
	return x;
}

啟發式合并

還是剛才那個思路，我們考慮樹上啟發式合并

我們還是考慮線段樹底層是操作次序\(k_i\)，那這樣我們需要將\(t_i\)插入進去，用區間減操作處理\(k\)的真實值，具體的講，將區間\([k_i+1,up]\)都減去1，代表它們在此節點后操作，注意初始線段樹來個極大值即可，然后區間取min

時間復雜度為\(O(n log^2 n)\),常數很小

貼一下初繪代碼

void pushup(int p) {tr[p] = min(tr[p * 2] , tr[p * 2 + 1]);}
void pushdown(int p) {/* ... */}
void change(int p , int l , int r , int s , int t , int x) {
    /*區間加減*/
}
void TJ(int x , int fa , int op) {
    change(1 , 1 , n , dis[x] , dis[x] , (a[x].t - M) * op);
    change(1 , 1 , n , dis[x] + 1 , n , (-1) * op);
    for(auto to : v[x]) {
        if(to == fa) continue;
        TJ(to , x , op); 
    }
}
void dfs2(int x , int fa , bool op) {
    for(auto to : v[x]) {
        if(to == fa || to == son[x]) continue;
        dfs2(to , x , 0); 
    }
    if(son[x]) dfs2(son[x] , x , 1);
    for(auto to : v[x]) {
        if(to == fa || to == son[x]) continue;
        TJ(to , x , 1);
    }
    change(1 , 1 , n , dis[x] , dis[x] , a[x].t - M);//插入自身
    change(1 , 1 , n , dis[x] + 1 , n , -1);//區間減，維護子樹內k值
    ans[x] = tr[1];
    if(!op) TJ(x , fa , -1);
}