【SDOI2015】寻宝游戏

代码

（树链剖分）

#include<cstdio>

#include<set>

using namespace std;

typedef long long LL;

const int N = 1e5;

int top[N + 5] , dfn[N + 5] , rev[N + 5] , fa[N + 5] , size[N + 5] , son[N + 5] , dep[N + 5];

LL dis[N + 5] , ans , now;

int vis[N + 5] , h[N + 5] , n , m , tot = 1 , cnt;

struct node1{

	int to , nxt , w;

}e[(N << 1) + 5];

set<int> list;

set<int>::iterator it;

inline int read()

{

	char ch = getchar();

	int res = 0;

	for(; ch < '0' || ch > '9'; ch = getchar());

	for(; ch >= '0' && ch <= '9'; ch = getchar()) res = (res << 3) + (res << 1) + ch - '0';

	return res;

}

inline void add(int x , int y , int z)

{

	e[++tot].to = y;

	e[tot].w = z;

	e[tot].nxt = h[x];

	h[x] = tot;

}

inline void dfs1(int x , int f , int d)

{

	dep[x] = d;

	dfn[x] = ++cnt;

	rev[cnt] = x;

	fa[x] = f;

	size[x] = 1;

	for(register int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == f) continue;

		dis[v] = dis[x] + 1LL * e[i].w;

		dfs1(v , x , d + 1);

		size[x] += size[v];

		if (size[v] > size[son[x]]) son[x] = v;

	}

}

inline void dfs2(int x , int f , int t)

{

	top[x] = t;

	if (son[x] > 0) dfs2(son[x] , x , t);

	for(register int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == f || v == son[x]) continue;

		dfs2(v , x , v);

	}

}

inline int query(int x , int y)

{

	int fx = top[x] , fy = top[y];

	while (fx != fy)

	{

		if (dep[fx] >= dep[fy]) x = fa[fx] , fx = top[x];

		else y = fa[fy] , fy = top[y];

	}

	if (dep[x] <= dep[y]) return x;

	return y;

}

inline LL ask(int x , int y)

{

	return dis[x] + dis[y] - 2 * dis[query(x , y)];

}

int main()

{

//	freopen("寻宝游戏.in" , "r" , stdin);

	n = read() , m = read();

	int x , y , z;

	for(register int i = 1; i < n; i++)

	{

		x = read() , y = read() , z = read();

		add(x , y , z) , add(y , x , z);

	}

	dfs1(1 , 0 , 1) , dfs2(1 , 0 , 1);

	for(register int i = 1; i <= m; i++)

	{

		x = read();

		x = dfn[x];

		if (!vis[rev[x]]) list.insert(x);

		y = rev[(it = list.lower_bound(x)) == list.begin() ? *--list.end() : *--it];

		z = rev[(it = list.upper_bound(x)) == list.end() ? *list.begin() : *it];

		if (vis[rev[x]]) list.erase(x);

		x = rev[x];

		now = ask(y , x) + ask(x , z) - ask(y , z);

		if (!vis[x]) vis[x] = 1 , ans += now;

		else vis[x] = 0 , ans -= now;

		printf("%lld\n" , ans);

	}

}

（倍增）

#include<cstdio>

#include<set>

using namespace std;

typedef long long LL;

const int N = 1e5;

int top[N + 5] , dfn[N + 5] , rev[N + 5] , fa[N + 5] , size[N + 5] , son[N + 5] , dep[N + 5];

LL dis[N + 5] , ans , now;

int vis[N + 5] , h[N + 5] , n , m , tot = 1 , cnt , f[N + 5][30];

struct node1{

	int to , nxt , w;

}e[(N << 1) + 5];

set<int> list;

set<int>::iterator it;

inline int read()

{

	char ch = getchar();

	int res = 0;

	for(; ch < '0' || ch > '9'; ch = getchar());

	for(; ch >= '0' && ch <= '9'; ch = getchar()) res = (res << 3) + (res << 1) + ch - '0';

	return res;

}

inline void add(int x , int y , int z)

{

	e[++tot].to = y;

	e[tot].w = z;

	e[tot].nxt = h[x];

	h[x] = tot;

}

inline int dfs(int x , int fa)

{

	dfn[x] = ++cnt;

	rev[cnt] = x;

	for(register int i = 1; i <= 25; i++)

	if (f[x][i - 1]) f[x][i] = f[f[x][i - 1]][i - 1];

	else break;

	for(register int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == fa) continue;

		dis[v] = dis[x] + e[i].w;

		dep[v] = dep[x] + 1 , f[v][0] = x , dfs(v , x);

	}

}

inline int LCA(int u , int v)

{

	if (dep[u] < dep[v]) swap(u , v);

	register int deep = dep[u] - dep[v];

	for(register int i = 0; i <= 25; i++)

	if ((1 << i) & deep) u = f[u][i];

	if (u == v) return u;

	for(register int i = 25; i >= 0; i--)

		if (f[u][i] != f[v][i]) u = f[u][i] , v = f[v][i];

	return f[u][0];

}

inline LL ask(int x , int y)

{

	return dis[x] + dis[y] - 2 * dis[LCA(x , y)];

}

int main()

{

//	freopen("寻宝游戏.in" , "r" , stdin);

	n = read() , m = read();

	int x , y , z;

	for(register int i = 1; i < n; i++)

	{

		x = read() , y = read() , z = read();

		add(x , y , z) , add(y , x , z);

	}

	dfs(1 , 0);

	for(register int i = 1; i <= m; i++)

	{

		x = read();

		x = dfn[x];

		if (!vis[rev[x]]) list.insert(x);

		y = rev[(it = list.lower_bound(x)) == list.begin() ? *--list.end() : *--it];

		z = rev[(it = list.upper_bound(x)) == list.end() ? *list.begin() : *it];

		if (vis[rev[x]]) list.erase(x);

		x = rev[x];

		now = ask(y , x) + ask(x , z) - ask(y , z);

		if (!vis[x]) vis[x] = 1 , ans += now;

		else vis[x] = 0 , ans -= now;

		printf("%lld\n" , ans);

	}

}

巴特西

【SDOI2015】寻宝游戏

代码

最新文章

热门文章