调了2个小时
查看原帖
调了2个小时
49677
miserExist楼主2021/7/14 21:49

希望有大佬看看哪里有问题

有的对有的不对

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2 * 300200;
const int INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx = 1;
int n,m;
int dep[N], fa[N], sz[N], son[N], tmp[N];
int id[N], nw[N],top[N], cnt;

struct node
{
	int l,r;
	int maxx, minn;
	int sum;
	int change;
}tr[N * 8];

struct p
{
	int x,y;
}lr[N * 8];

void add(int a,int b,int c)
{
	e[idx] = b;
	ne[idx] = h[a];	
	w[idx] = c;
	h[a] = idx ++;
}

void dfs1(int u,int father,int depth)
{
	dep[u] = depth;
	fa[u] = father;
	sz[u] = 1;
	for(int i = h[u]; ~i; i = ne[i])
	{
		int y = e[i];
		if(y == father)continue;
		dfs1(y, u, depth + 1);
		tmp[y] = w[i];
		sz[u] += sz[y];
		if(sz[son[u]] < sz[y])son[u] = y;
	}
}

void dfs2(int u,int t)//top?
{
	top[u] = t;
	id[u] =  ++ cnt; 
	nw[cnt] = tmp[u];
	//nw[cnt] = w[u];
	if(son[u])dfs2(son[u], t);
	for(int i = h[u]; ~i; i = ne[i])
	{
		int y = e[i];
		if(y == fa[u] || y == son[u])continue;
		dfs2(y, y);
	}
	
}
void pushup(int u)
{
	tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
	tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
	if(tr[u].change)
	{
		tr[u << 1 | 1].change ^= 1;
		tr[u << 1].change ^= 1;
		tr[u << 1].sum = tr[u << 1].sum * (-1);
		tr[u << 1 | 1].sum = tr[u << 1 | 1].sum * (-1);
		tr[u << 1].maxx  = -tr[u << 1].maxx;
		tr[u << 1 | 1].maxx  = -tr[u << 1 | 1].maxx;
		tr[u << 1].minn  = -tr[u << 1].minn;
		tr[u << 1 | 1].minn  = -tr[u << 1 | 1].minn;
		swap(tr[u << 1].minn,tr[u << 1].maxx);
		swap(tr[u << 1 | 1].minn,tr[u << 1 | 1].maxx );
		tr[u].change = 0;
	}

	
}

void build(int u,int l,int r)
{
	tr[u].l = l, tr[u].r = r;
	if(l == r)
	{
		tr[u].sum = nw[l];
		tr[u].maxx = nw[l];
		tr[u].minn = nw[l];
		tr[u].change = 0;
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify_single(int u,int pos, int k)
{
	if(tr[u].l == tr[u].r && tr[u].l == pos)
	{
		tr[u].sum = k;
		tr[u].maxx = k;
		tr[u].minn = k;
		return;
	}
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(pos <= mid)modify_single(u << 1,pos,k);
	if(pos > mid)modify_single(u << 1 | 1, pos, k);
	pushup(u);
}


int query_maxx(int u,int l,int r)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		return tr[u].maxx;
	}
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	int MAXX = -INF;
	if(l <= mid)MAXX = max(MAXX, query_maxx(u << 1, l, r));
	if(r > mid)MAXX = max(MAXX, query_maxx(u << 1 | 1, l, r));
	pushup(u);
	return MAXX;
}

int query_minn(int u,int l,int r)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		return tr[u].minn;
	}
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	int MINN = INF;
	if(l <= mid)MINN = min(MINN, query_minn(u << 1, l, r));
	if(r > mid)MINN = min(MINN, query_minn(u << 1 | 1, l, r));
	pushup(u);
	return MINN;
}

void modify_range(int u,int l,int r)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].sum = -tr[u].sum;
		tr[u].maxx = -tr[u].maxx;
		tr[u].minn = -tr[u].minn;
		swap(tr[u].maxx, tr[u].minn);
		tr[u].change ^= 1;
		return;
	}
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid)modify_range(u << 1,l,r);
	if(r > mid)modify_range(u << 1 | 1,l,r);
	pushup(u);
}

int query_sum(int u,int l,int r)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		return tr[u].sum;
	}
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	int ans = 0;
	if(l <= mid)ans += query_sum(u << 1, l, r);
	if(r > mid)ans += query_sum(u << 1 | 1, l,r );
	pushup(u);
	return ans;
}

void modify_r(int u,int v)
{
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]])swap(u,v);
		modify_range(1,id[top[u]],id[u]);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v])swap(u,v);
	//if(u != v) moadify_range(1,id[v],id[u]);
	if(u != v)modify_range(1, id[u] + 1, id[v]);
}
int query_ma(int u,int v)
{
	int MAXX = -INF;
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]])swap(u,v);
		MAXX = max(MAXX, query_maxx(1, id[top[u]], id[u]));
		u = fa[top[u]];
	}
	if(dep[u] > dep[v])swap(u,v);
	if(u != v)MAXX = max(MAXX, query_maxx(1, id[u] + 1, id[v]));
	return MAXX; 
}
int query_mi(int u,int v)
{
	int MINN = INF;
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]])swap(u,v);
		MINN = min(MINN, query_minn(1,id[top[u]], id[u]));
		u = fa[top[u]];
	}
	if(dep[u] > dep[v])swap(u,v);
	if(u != v)MINN = min(MINN, query_minn(1, id[u] + 1,id[v]));
	return MINN;
}

int query_s(int u,int v)
{
	int ans = 0;
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]])swap(u,v);
		ans += query_sum(1, id[top[u]], id[u]);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v])swap(u,v);
	if(u != v)ans += query_sum(1, id[u] + 1, id[v]);
	return ans;
}

signed main()
{
	memset(h , -1, sizeof h);
	scanf("%lld", &n);
	for(int i = 1; i <= n - 1; i ++)
	{
		int a,b,c;
		scanf("%lld%lld%lld", &a, &b, &c);
		add(a + 1,b + 1,c);
		add(b + 1,a + 1,c);
		lr[i].x = a, lr[i].y = b;
	}
	//+ 1
	dfs1(1,0,1);
	dfs2(1,1);
	build(1,1,n);
	
	scanf("%lld", &m);
	while(m --)
	{
		char op[10];
		int l,r,k;
		scanf("%s", op);
		if(op[0] == 'C')
		{
			int com;
			scanf("%lld%lld", &l, &k);
			if(dep[lr[l].x] > dep[lr[l].y])com = lr[l].x;
			else com = lr[l].y;
			//modify_s(1, id[l + 1], k);
			modify_single(1, id[com], k);
		}
		else if(op[0] == 'N')
		{
			scanf("%lld%lld", &l, &r);
			//modify_r(1, id[l + 1], id[r + 1]);
			modify_r(l + 1, r + 1);
		}
		else if(op[0] == 'M' && op[1] == 'A')
		{
			scanf("%lld%lld", &l, &r);
			//printf("%d\n", query_max(1,id[l + 1], id[r + 1]));
			printf("%lld\n", query_ma(l + 1, r + 1));
		}
		else if(op[0] == 'S')
		{
			scanf("%lld%lld", &l, &r);
			//printf("%d\n", query_sum(1,id[l + 1], id[r + 1]));
			printf("%lld\n", query_s(l + 1, r + 1));
		}
		else if(op[0] == 'M' && op[1] == 'I')
		{
			scanf("%lld%lld", &l, &r);
			//printf("%d\n", query_min(1,id[l + 1], id[r + 1]));
			printf("%lld\n", query_mi(l + 1, r + 1));
		}
	}
	
	
	return 0;
}
2021/7/14 21:49
加载中...