Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

树链剖分+线段树+单点更新+拆边

Posted by a280920481 at 2019-07-12 15:58:53 on Problem 2763
#include <algorithm>
using namespace std;


const int MAX_N = 200008;
struct Edge
{
	int to;
	int next;
	Edge(const int& to, const int& next)
		:to(to), next(next) {}
	Edge() :to(-1), next(-1) {}
}G[2 * MAX_N];
int head[MAX_N];
int deg;

int cnt;
int par[MAX_N];
int depth[MAX_N];
int scnt[MAX_N];
int rk[MAX_N];
int top[MAX_N];
int id[MAX_N];
int son[MAX_N];

int init_t(const int n);
void add_edge(const int& u, const int& v);

void dfs1(const int v);
void dfs2(const int v, const int tp);

int _n;
int dat[1 << 19];
void init(const int n);
int query(const int& left, const int& right, const int k, const int begin, const int end);
void update(int p, const int& x);

int query(int x, int y);

int A[MAX_N];


int main()
{
	int n, q, s, a, b, w, op;
	scanf("%d%d%d", &n, &q, &s);
	--s;

	int ecnt = n;
	const int n2 = 2 * n - 1;
	init_t(n2);
	for (int i = 1; i < n; ++i)
	{
		scanf("%d%d%d", &a, &b, &w);
		--a; --b;
		add_edge(a, ecnt);
		add_edge(ecnt, b);
		A[ecnt++] = w;
	}

	int root = 0;
	dfs1(root);
	dfs2(root, root);

	init(n2);
	while (q--)
	{
		scanf("%d%d", &op, &a);
		--a;

		if (op)
		{
			scanf("%d", &w);
			update(id[n + a], w);
		}
		else
		{
			printf("%d\n", query(s, a));
			s = a;
		}
	}
	return 0;
}

int init_t(const int n)
{
	par[0] = deg = cnt = 0;
	fill(son, son + n + 1, -1);
	fill(head, head + n + 1, -1);
	return 0;
}

void add_edge(const int& u, const int& v)
{
	G[deg] = Edge(v, head[u]);
	head[u] = deg++;
	G[deg] = Edge(u, head[v]);
	head[v] = deg++;
}

void dfs1(const int v)
{
	scnt[v] = 1;
	depth[v] = depth[par[v]] + 1;
	int maxson = -1;
	for (int i = head[v]; ~i; i = G[i].next)
	{
		const int& to = G[i].to;
		if (to != par[v])
		{
			par[to] = v;
			dfs1(to);
			scnt[v] += scnt[to];
			if (scnt[to] > maxson)
			{
				maxson = scnt[to];
				son[v] = to;
			}
		}
	}
}

void dfs2(const int v, const int tp)
{
	top[v] = tp;
	id[v] = cnt;
	rk[cnt++] = v;

	if (~son[v])
	{
		dfs2(son[v], tp);
		for (int i = head[v]; ~i; i = G[i].next)
		{
			const int& to = G[i].to;
			if (to != par[v] && to != son[v])
			{
				dfs2(to, to);
			}
		}
	}
}

void init(const int n)
{
	_n = 1;
	while (_n < n)
	{
		_n <<= 1;
	}
	--_n;

	for (int i = 0; i < n; ++i)
	{
		dat[_n + i] = A[rk[i]];
	}
	for (int i = _n - 1; i >= 0; --i)
	{
		dat[i] = dat[(i << 1) + 1] + dat[(i << 1) + 2];
	}
}

int query(const int& left, const int& right, const int k, const int begin, const int end)
{
	if (left <= begin && end <= right)
	{
		return dat[k];
	}
	else if (left <= end && begin <= right)
	{
		return query(left, right, (k << 1) + 1, begin, (begin + end) >> 1) +
			query(left, right, (k << 1) + 2, ((begin + end) >> 1) + 1, end);
	}
	else return 0;
}

void update(int p, const int& x)
{
	p += _n;
	int d = x - dat[p];
	dat[p] = x;
	while (p)
	{
		p = (p - 1) >> 1;
		dat[p] += d;
	}
}

int query(int x, int y)
{
	int s = 0;
	while (top[x] != top[y])
	{
		if (depth[top[x]] < depth[top[y]])
		{
			swap(x, y);
		}
		s += query(id[top[x]], id[x], 0, 0, _n);
		x = par[top[x]];
	}
	if (id[x] < id[y])
	{
		swap(x, y);
	}
	s += query(id[y], id[x], 0, 0, _n);
	return s;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator