大连大学2024.4校赛G题题解

G题作为本场校赛的压轴题，通过人数比较少。

赛前测试的时候，std在牛客的评测机上大概时间为2s左右，遂开了1.5倍时限，可能有点卡常。但std本身没有做多余剪枝，正常的写法只要常数不太大应该都能通过。

空间限制是为了看看有没有其他神秘做法，根据赛中情况来看好像没有。

贴一张std运行时间，牛客神机还是跑的很快的

简要题意：

给一棵个节点的树，每个节点有一个持续时间（代表在第秒的开始塌陷），第秒可以进行两个操作的其中之一

，对于所有与距离的节点，若未塌陷，则将的持续时间与比较，若后者更大，则把的值修改为

，询问节点是否塌陷

塌陷的节点不会恢复

solution：

考虑对距离的节点进行维护。因为每次修改均涉及的是相邻节点，这启发我们使用BFS序+高级数据结构维护

在BFS序中，一个节点的儿子的下标是连续的，所以我们可以把距离的所有点拆分为不超过个区间：

1. 的儿子
2. 的孙子（因为的儿子在BFS序中连续，所以的孙子也在BFS序中连续）
3. 的兄弟
4. 自身
5. 的父亲
6. 的爷爷

进行区间分割后，我们可以通过一次DFS来求出对于所有节点距离的区间集合。

接下来考虑对区间的维护：

发现本质上是区间取，可以使用带懒标记的线段树来维护，对于在每一秒开始要塌陷的节点，我们直接暴力递归到叶子，开一个数组记录是否塌陷，并把的持续时长改为（一个很大的数），对于操作，修改所有区间，对于操作，直接根据数组的值来判断。

暴力递归部分的次数不会超过次，总体时间复杂度为

std

#include <bits/stdc++.h>
using namespace std ;
using ll = long long ;
using pii = pair<int, int> ;
const int N = 2e5 + 5, INF = 1e9 ;

int n, m ;
vector<int> g[N] ;
int lst[N] ;
int dfn[N], fa[N], rev[N], num ;
bool vis[N], deled[N] ;
int ld1[N], rd1[N], ld2[N], rd2[N] ;
struct SegmentTree
{
	int l, r ;
	int minv, lazy_max ;
} t[N << 2] ;

void chmax(int &x, int y) { if(x < y) x = y ; }

void pushup(int p)
{
	t[p].minv = min(t[p << 1].minv, t[p << 1 | 1].minv) ;
}

void pushdown(int p)
{
	if(t[p].lazy_max)
	{
		chmax(t[p << 1].minv, t[p].lazy_max) ;
		chmax(t[p << 1 | 1].minv, t[p].lazy_max) ;
		chmax(t[p << 1].lazy_max, t[p].lazy_max) ;
		chmax(t[p << 1 | 1].lazy_max, t[p].lazy_max) ;
		t[p].lazy_max = 0 ;
	}
}

void build(int p, int l, int r)
{
	t[p].l = l ; t[p].r = r ; 
	t[p].minv = INF ; t[p].lazy_max = 0 ;
	if(l == r)
	{
		t[p].minv = lst[rev[l]] ;
		return ;
	}
	int mid = (t[p].l + t[p].r) >> 1 ;
	build(p << 1, l, mid) ; build(p << 1 | 1, mid + 1, r) ;
	pushup(p) ;
}

void delNodes(int p, int v)
{
	if(t[p].minv > v) return ;
	if(t[p].l == t[p].r)
	{
		deled[rev[t[p].l]] = 1 ;
		t[p].minv = INF ;
		return ;
	}
	pushdown(p) ;
	delNodes(p << 1, v) ;
	delNodes(p << 1 | 1, v) ;
	pushup(p) ;
}

void rangeMax(int p, int l, int r, int d)
{
	if(l <= t[p].l && t[p].r <= r)
	{
		chmax(t[p].lazy_max, d) ;
		chmax(t[p].minv, d) ;
		return ;
	}
	pushdown(p) ;
	int mid = (t[p].l + t[p].r) >> 1 ;
	if(l <= mid) rangeMax(p << 1, l, r, d) ;
	if(r > mid) rangeMax(p << 1 | 1, l, r, d) ;
	pushup(p) ;
}

void dfs(int x, int f)
{
	ld1[x] = ld2[x] = INF ;
	rd1[x] = rd2[x] = -INF ;
	fa[x] = f ;
	for(auto y : g[x]) if(y != f)
	{
		dfs(y, x) ;
		ld1[x] = min(ld1[x], dfn[y]) ;
		rd1[x] = max(rd1[x], dfn[y]) ;
		ld2[x] = min(ld2[x], ld1[y]) ;
		rd2[x] = max(rd2[x], rd1[y]) ;
	}
}

void getRanges(int x, vector<pii> &vec)
{
	int y = fa[x], z = fa[y] ;
	vec.push_back({dfn[x], dfn[x]}) ; // x
	vec.push_back({ld1[x], rd1[x]}) ; // son[x]
	vec.push_back({ld2[x], rd2[x]}) ; // son_son[x]
	if(y)
	{
		vec.push_back({ld1[y], rd1[y]}) ; // brother[x]
		vec.push_back({dfn[y], dfn[y]}) ; // fa[x]
		if(z) vec.push_back({dfn[z], dfn[z]}) ; // fa_fa[x]
	}
}

void solve()
{
    cin >> n >> m ;
    for(int i = 1; i <= n; ++ i)
    {
    	g[i].clear() ;
    	vis[i] = 0 ;
    	deled[i] = 0 ;
    }
    for(int i = 1; i < n; ++ i)
    {
    	int x, y ; cin >> x >> y ;
    	g[x].push_back(y) ;
    	g[y].push_back(x) ;
    }
    for(int i = 1; i <= n; ++ i) cin >> lst[i] ;
    num = 0 ;

	queue<int> q ; q.push(1) ;
	while(!q.empty())
	{
		int x = q.front() ; q.pop() ;
		vis[x] = 1 ;
		dfn[x] = ++ num ;
		rev[num] = x ;
		for(auto y : g[x])
			if(!vis[y]) q.push(y) ;
	}
	dfs(1, 0) ;
	build(1, 1, n) ;

	for(int i = 1; i <= m; ++ i)
	{
		delNodes(1, i) ;
		int opt ; cin >> opt ;
		if(opt == 1)
		{
			int x, t ; cin >> x >> t ;
			vector<pii> vec ;
			getRanges(x, vec) ;
			for(auto [l, r] : vec)
				if(l <= r) rangeMax(1, l, r, i + t) ;
		}
		else
		{
			int x ; cin >> x ;
			cout << (deled[x] ? "YES" : "NO") << '\n' ;
		}
	}
}

signed main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    int T ; cin >> T ;
    while(T --) solve() ;
    return 0 ;
}