牛客挑战赛57C题解

登录—专业IT笔试面试备考平台_牛客网

最近题刷了一堆，结果碰上这种裸的数据结构题（套路题）不会做了（场上想了个对询问分块，还去搞了个O(1)求k级祖先，结果被卡爆）......remake吧。

直接大力树剖，每条修改的链被划分为log段，向上的修改存在孩子处，向下的存在父亲处，注意向上的时候跳轻边处理下即可。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) (x).begin(), (x).end()
#define VI vector<int>
#define VLL vector<ll>
#define pll pair<ll, ll>
#define double long double
//#define int long long
using namespace std;
const int N = 1e6 + 100;
const int inf = 1e9;
const ll mod = 998244353;//1e9 + 7;

#ifdef LOCAL
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int n, qnum;
ll a[N];
VI adj[N];

int gson[N], sz[N], dep[N], fa[N];

void dfs0(int x, int ff)
{
	fa[x] = ff;
	sz[x] = 1;
	trav(v, adj[x])
	{
		if(v == ff)
			continue;
		dep[v] = dep[x] + 1;
		dfs0(v, x);
		sz[x] += sz[v];
		if(sz[v] > sz[gson[x]])
			gson[x] = v;
	}
}

int top[N], dfn[N], tim;

void dfs1(int x, int tp, int ff)
{
	top[x] = tp;
	dfn[x] = ++tim;
	if(gson[x])
	{
		dfs1(gson[x], tp, x);
		trav(v, adj[x])
		{
			if(v == ff || v == gson[x])
				continue;
			dfs1(v, v, x);
		}
	}
}

int cal_lca(int x, int y)
{
	int tx, ty;
	tx = top[x], ty = top[y];
	while(tx != ty)
	{
		if(dep[tx] < dep[ty])
			swap(x, y), swap(tx, ty);
		x = fa[tx];
		tx = top[x];
	}
	return dep[x] <= dep[y] ? x : y;
}

int fen[2][N];
ll val[N];

void add(int op, int l, int r)
{
	++r;
	for(; l <= tim; l += l & -l)
		fen[op][l]++;
	for(; r <= tim; r += r & -r)
		fen[op][r]--;
}

ll ask(int op, int x)
{
	ll res = 0;
	for(; x; x -= x & -x)
		res += fen[op][x];
	return res;
}

void doit(int op, int x, int y)
{
	if(x == y)
		return;
	int tx = top[x];
	while(1)
	{
		if(dep[tx] <= dep[y])
		{
			int lp = dfn[gson[y]];
			int rp = dfn[x];
			add(op, lp, rp);
			break;
		}
		else
		{
			int lp = dfn[tx];
			int rp = dfn[x];
			add(op, lp, rp);
			int fx = fa[tx];
			if(op == 0)
				val[fx] += a[tx];
			x = fx;
			tx = top[x];
		}
	}
}

void sol()
{
	cin >> n >> qnum;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	dep[1] = 1, dfs0(1, 0);
	dfs1(1, 1, 0);
	while(qnum--)
	{
		int op;
		cin >> op;
		if(op == 1)
		{
			int x, y;
			cin >> x >> y;
			//cerr << "!!!!!!" << op << ' ' << x << ' ' << y << '\n';
			int lca = cal_lca(x, y);
			// /cerr << lca << '\n';
			doit(0, x, lca);
			doit(1, y, lca);
		}
		else
		{
			int x;
			cin >> x;
			//cerr << ">>" << op << ' ' << x << '\n';
			ll res = 0;
			res = val[x];
			if(gson[x])
				res += ask(0, dfn[gson[x]]) * a[gson[x]];
			res += ask(1, dfn[x]) * a[fa[x]];
			cout << res << '\n';
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
//	int tt;
//	cin >> tt;
//	while(tt--)
		sol();
}