题目描述

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。

爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：

Change k w：将第k条树枝上毛毛果的个数改变为w个。

Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。

Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问：

Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

输入格式

第一行一个正整数N。

接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。接下来是操作和询问，以“Stop”结束。

输出格式

对于毛毛虫的每个询问操作，输出一个答案。

输入输出样例

输入 #1

4

1 2 8

1 3 7

3 4 9

Max 2 4

Cover 2 4 5

Add 1 4 10

Change 1 16

Max 2 4

Stop

输出 #1

9

16

说明/提示

1<=N<=100,000，操作+询问数目不超过100,000。

保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。

这个题是道树剖的好题（毒瘤题，debug就要抵好长时间）。

首先，我们要进行边转点的操作。

接着，我们要考虑每一个操作。

这个题要求我们支持区间修改，单点修改，区间加，区间最大值的操作。

对于区间修改和单点修改，我们直接维护一个tag标记。

区间加的操作维护一个add标记。

下放时，tag标记的优先级要高于add标记。在下放完tag标记后，要把add标记清空，便于后面的操作。

剩下的就是线段树和树剖的模板了。

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 1e5+10;

string opt;

int n,m,u,v,tot,num,val,x,y;

int size[N],son[N],fa[N],from[N],to[N],head[N],dfn[N],dep[N],a[N],w[N],top[N];

inline int read()

{

	int s = 0, w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9'){s = s * 10+ch -'0'; ch = getchar();}

	return s * w;

}

struct node{int to,net,w;}e[N<<1];

void add_(int x,int y,int w)//建边

{

	e[++tot].w = w;

	e[tot].to = y;

	e[tot].net = head[x];

        head[x] = tot;

}

void get_tree(int x)//树剖

{

	dep[x] = dep[fa[x]] + 1; size[x] = 1;

	for(int i = head[x]; i; i = e[i].net)

	{

		int to = e[i].to;

		if(to == fa[x]) continue;

		fa[to] = x; a[to] = e[i].w;

		get_tree(to);

		size[x] += size[to];

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

	}

}

void dfs(int x,int topp)

{

	top[x] = topp;  dfn[x] = ++num; w[dfn[x]] = a[x];

	if(son[x]) dfs(son[x],topp);

	for(int i = head[x]; i; i = e[i].net)

	{

		int to  = e[i].to;

		if(to == fa[x] || to == son[x]) continue;

		dfs(to,to);

	}

}

struct Tree

{

	struct node{

		int lc,rc;

		int add,maxn,tag;

	}tr[N<<2];

	#define l(o) tr[o].lc

	#define r(o) tr[o].rc

	#define add(o) tr[o].add

	#define tag(o) tr[o].tag

	#define maxn(o) tr[o].maxn

	void up(int o)

	{

		maxn(o) = max(maxn(o<<1),maxn(o<<1|1));

	}

	void cover(int o,int val){tag(o) = val; maxn(o) = val;}//维护tag标记

	void Add(int o,int val){add(o)+= val; maxn(o) += val;}//维护add标记

	void down(int o)

	{

        if(tag(o) != -1)//如果有标记

        {

           add(o<<1) = add(o<<1|1) = 0;//add标记要清空

           cover(o<<1,tag(o)); cover(o<<1|1,tag(o));

           tag(o) = -1;

        }

        if(add(o))

        {

            Add(o<<1,add(o)); Add(o<<1|1,add(o));

           add(o) = 0;

        }

	}

	void build(int o,int L,int R)

	{

		l(o) = L, r(o) = R; tag(o) = -1;//tag标记初始化为-1，即没有标记

		if(L == R)

		{

			maxn(o) = w[L]; return;

		}

		int mid = (L+R)>>1;

		build(o<<1,L,mid);

		build(o<<1|1,mid+1,R);

		up(o);

	}

	void chenge(int o,int L,int R,int val)//区间修改

	{

		if(L <= l(o) && R >= r(o))

		{

			cover(o,val);

			add(o) = 0; return;//add标记清零

		}

		down(o);

		int mid = (l(o) + r(o))>>1;

		if(L <= mid) chenge(o<<1,L,R,val);

		if(R > mid) chenge(o<<1|1,L,R,val);

		up(o);

	}

	void change(int o,int L,int R,int val)//区间加

	{

		if(L <= l(o) && R >= r(o))

		{

		   Add(o,val); return;

		}

		down(o);

		int mid = (l(o) + r(o))>>1;

		if(L <= mid) change(o<<1,L,R,val);

		if(R > mid) change(o<<1|1,L,R,val);

		up(o);

	}

	int ask(int o,int L,int R)//询问区间最大值

	{

		int ans = 0;

		if(L <= l(o) && R >= r(o)){return maxn(o);}

		down(o);

		int mid = (l(o) + r(o))>>1;

		if(L <= mid) ans = max(ans,ask(o<<1,L,R));

		if(R > mid) ans = max(ans,ask(o<<1|1,L,R));

		return ans;

	}

}tree;

void cover(int x,int y,int val)//跳链修改

{

	while(top[x] != top[y])

	{

		if(dep[top[x]] < dep[top[y]]) swap(x,y);

		tree.chenge(1,dfn[top[x]],dfn[x],val);

		x = fa[top[x]];

	}

	if(dep[x] > dep[y]) swap(x,y);

	tree.chenge(1,dfn[x]+1,dfn[y],val);

}

void jia(int x,int y,int val)//跳链加

{

	while(top[x] != top[y])

	{

		if(dep[top[x]] < dep[top[y]]) swap(x,y);

		tree.change(1,dfn[top[x]],dfn[x],val);

		x = fa[top[x]];

	}

	if(dep[x] > dep[y]) swap(x,y);

	tree.change(1,dfn[x]+1,dfn[y],val);

}

int query(int x,int y)

{

	int ans = 0;

	while(top[x] != top[y])

	{

		if(dep[top[x]] < dep[top[y]]) swap(x,y);

		ans = max(ans,tree.ask(1,dfn[top[x]],dfn[x]));

		x = fa[top[x]];

	}

	if(dep[x] > dep[y]) swap(x,y);

	ans = max(ans,tree.ask(1,dfn[x]+1,dfn[y]));

	return ans;

}

int main()

{

	n = read();

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

	{

		u = read(); v = read(); val = read();

		add_(u,v,val); add_(v,u,val);

		from[i] = u; to[i] = v;

	}

	get_tree(1); dfs(1,1); tree.build(1,1,n);

	while(1)

	{

		cin>>opt;

		if(opt == "Stop") break;

		if(opt == "Change")

		{

			x = read(); val = read();

			int xx = from[x];

			int yy = to[x];

			if(fa[xx] == yy) tree.chenge(1,dfn[xx],dfn[xx],val);

			else tree.chenge(1,dfn[yy],dfn[yy],val);

		}

		if(opt == "Cover")

		{

			x = read(); y = read(); val = read();

			cover(x,y,val);

		}

		if(opt == "Add")

		{

			x = read(); y = read(); val = read();

			jia(x,y,val);

		}

		if(opt == "Max")

		{

			x = read(); y = read();

			printf("%d\n",query(x,y));

		}

	}

	return 0;

}

这道题真是毒瘤，对于标记的下放就特别容易搞混。（debug花了我一个多小时）

巴特西

P 4315 月下毛景树

题目描述

输入格式

输出格式

输入输出样例

说明/提示

ENDING

最新文章

热门文章