結果

問題 No.899 γatheree
コンテスト
ユーザー zengyongxu-jerry
提出日時 2026-08-27 17:02:44
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,643 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,160 ms
コンパイル使用メモリ 369,064 KB
実行使用メモリ 22,016 KB
最終ジャッジ日時 2026-08-27 17:02:58
合計ジャッジ時間 11,837 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:128:3: warning: backslash-newline at end of file
  128 | //\

ソースコード

diff #
raw source code 

// <DATETIME>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define rep(i, x, y) for (int i = (x); i <= (y); i ++ )
#define per(i, x, y) for (int i = (x); i >= (y); i -- )
const int N = 5e5 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18, RMX = 2324814;
mt19937 rd(time(0));
uniform_int_distribution<int> dist(0, RMX);

int n, a[N];
vector <int> fvv[N], g[N];

struct segment{
	int tr[N << 2], laz[N << 2];
	void pushup(int now){
		tr[now] = tr[now << 1] + tr[now << 1 | 1];
	}
	void pushdown(int now){
		if (laz[now]) tr[now << 1] = 0, laz[now << 1] = 1, tr[now << 1 | 1] = 0, laz[now << 1 | 1] = 1, laz[now] = 0;
	}
	void modify_clr(int now, int l, int r, int lt, int rt){
		if (lt <= l && r <= rt){
			tr[now] = 0, laz[now] = 1;
			return ;
		}
		pushdown(now);
		int mid = (l + r) >> 1;
		if (lt <= mid) modify_clr(now << 1, l, mid, lt, rt);
		if (mid < rt) modify_clr(now << 1 | 1, mid + 1, r, lt, rt);
		pushup(now);
	}
	void modify_pt(int now, int l, int r, int pos, int x){
		if (l == r){
			tr[now] = x;
			return ;
		}
		pushdown(now);
		int mid = (l + r) >> 1;
		if (pos <= mid) modify_pt(now << 1, l, mid, pos, x);
		else modify_pt(now << 1 | 1, mid + 1, r, pos, x);
		pushup(now);
	}
	int query(int now, int l, int r, int lt, int rt){
		if (lt <= l && r <= rt) return tr[now];
		pushdown(now);
		int mid = (l + r) >> 1;
		if (rt <= mid) return query(now << 1, l, mid, lt, rt);
		if (mid < lt) return query(now << 1 | 1, mid + 1, r, lt, rt);
		return query(now << 1, l, mid, lt, rt) + query(now << 1 | 1, mid + 1, r, lt, rt);
	}
} seg;

int pos[N], id[N], tot, fa[N], dep[N];
void dfs(int f, int u){
	dep[u] = dep[f] + 1, fa[u] = f;
	fvv[dep[u]].push_back(u);
	for (auto v : g[u]){
		if (v == f) continue;
		dfs(u, v);
	}
}

int mn1[N], mx1[N];
int mn2[N], mx2[N];

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    cin >> n;
    rep(i, 1, n - 1){
		int u, v; cin >> u >> v;
		u ++, v ++ ;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	rep(i, 1, n) cin >> a[i];
	
	dfs(0, 1);
	
	rep(i, 1, n) mn1[i] = mn2[i] = inf, mx1[i] = mx2[i] = -inf;
	rep(i, 1, n){
		for (auto u : fvv[i]) pos[u] = ++ tot, id[tot] = u;
	}
	rep(u, 1, n){
		if (fa[u]) mn1[fa[u]] = min(mn1[fa[u]], pos[u]);
		if (fa[fa[u]]) mn2[fa[fa[u]]] = min(mn2[fa[fa[u]]], pos[u]);
		if (fa[u]) mx1[fa[u]] = max(mx1[fa[u]], pos[u]);
		if (fa[fa[u]]) mx2[fa[fa[u]]] = max(mx2[fa[fa[u]]], pos[u]);
		seg.modify_pt(1, 1, n, pos[u], a[u]);
	}
	
	int q; cin >> q;
	while (q -- ){
		int u; cin >> u;
		u ++ ;
		
		vector <pii> rg;
		if (mn1[u] <= mx1[u]) rg.push_back({mn1[u], mx1[u]});
		if (mn2[u] <= mx2[u]) rg.push_back({mn2[u], mx2[u]});
		if (fa[u]){
			rg.push_back({pos[fa[u]], pos[fa[u]]});
			if (mn1[fa[u]] <= mx1[fa[u]]) rg.push_back({mn1[fa[u]], mx1[fa[u]]});
		}
		if (fa[fa[u]]) rg.push_back({pos[fa[fa[u]]], pos[fa[fa[u]]]});
		
		int sum = 0;
		for (auto qwq : rg){
			int l = qwq.fi, r = qwq.se;
			sum += seg.query(1, 1, n, l, r);
		}
		for (auto qwq : rg){
			int l = qwq.fi, r = qwq.se;
			seg.modify_clr(1, 1, n, l, r);
		}
		seg.modify_pt(1, 1, n, pos[u], sum);
		cout << sum << "\n";
	}
}

//\
这个题目就是说，距离 x 为 1, 2 的点的值之和为 ans，然后将这些点的值清零，x 的值设为 ans 即可\
然后考虑 x 距离为 1 就是，x 的子节点 + x 的父节点\
距离为 2 就是，x 的子树中 dep = dep[x] + 2 的点，fa[x] 的所有子节点，fa[fa[x]]\
然后我们考虑用一种方法使得这些东西构成连续区间\
疑似层序遍历即可。\
0