又疯一个,动态树+线段树分治调不出来了/kk。
查看原帖
又疯一个,动态树+线段树分治调不出来了/kk。
227824
JK_LOVER楼主2020/7/27 19:28
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x = 0,f = 0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}
const int N = 3101000;
int n,m;
struct LinkCutTree{
	int c[2],val,mx,fa;
	bool r;
}t[N];
bool nroot(int x)
{
	return t[t[x].fa].c[1] == x || t[t[x].fa].c[0] == x;
}
void pushr(int x)
{
	swap(t[x].c[1],t[x].c[0]);
	t[x].r ^= 1;
}
void pushdown(int x)
{
	if(t[x].r)
	{
		if(t[x].c[1]) pushr(t[x].c[1]);
		if(t[x].c[0]) pushr(t[x].c[0]);
		t[x].r = 0;
	}
}
void push(int x)
{
	if(nroot(x)) push(t[x].fa);
	pushdown(x);
}
void pushup(int x)
{
	if(x > n) t[x].mx = x;
	else t[x].mx = 0;
	if(t[t[t[x].c[1]].mx].val > t[t[x].mx].val) t[x].mx = t[t[x].c[1]].mx;  
	if(t[t[t[x].c[0]].mx].val > t[t[x].mx].val) t[x].mx = t[t[x].c[0]].mx; 
}
void rotate(int x)
{
	int y = t[x].fa,z = t[y].fa,k = (t[y].c[1] == x),w = t[x].c[!k];
	if(nroot(y)) t[z].c[t[z].c[t[z].c[1] == y]] = x;
	t[x].c[!k] = y;t[y].c[k] = w;
	t[x].fa = z;if(w)t[w].fa = y;t[y].fa = x;
	pushup(y);
}
void splay(int x)
{
	push(x);
	while(nroot(x))
	{
//		cout<<x<<endl;
		int y = t[x].fa,z = t[y].fa;
		if(nroot(y))
		{
			rotate(((t[z].c[1] == y)^(t[y].c[1] == x))?x:y);
		}
		rotate(x);
		pushup(x);
	}
}
void access(int x)
{
	for(int y = 0;x;x = t[y].fa)
	{
		splay(x);t[x].c[1] = y;pushup(x);y = x;
	}
}
void makeroot(int x)
{
	access(x);splay(x);pushr(x);
}
void split(int x,int y)
{
	makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
	split(x,y);
	t[x].fa = y;
}
void cut(int x,int y)
{
	split(x,y);
	t[y].c[0] = t[x].fa = 0;
	pushup(y);
}
struct Edge{int x,y,w;}e[N];
struct Stack{int x,y;}st[N];
int top = 0,tot = 0;
vector<int> T[N];
void update(int u,int l,int r,int L,int R,int x)
{
	if(r < L || l > R) return;
	if(L <= l && r <= R) {T[u].push_back(x);return;}
	int mid = l + r >> 1;
	update(u<<1,l,mid,L,R,x);
	update(u<<1|1,mid+1,r,L,R,x);
}
void solve(int u,int l,int r)
{
//	cout<<u<<endl;
	int lasttop = top;
	for(int i = 0;i < T[u].size();i++)
	{
		int id = T[u].at(i);
		int a = e[id].x,b = e[id].y,w = e[id].w;
		split(a,b);
		int Emax;
		Emax = t[b].mx - n;
//		cout<<Emax<<" id:: "<<t[Emax].val<<endl;
		if(t[Emax].val <= w) continue;
		st[++top] = (Stack){Emax,id};
		tot -= e[Emax].w;
		cut(a,Emax+n);cut(b,Emax+n);
		tot += e[id].w;
		link(a,id+n);link(b,id+n);
	}
	if(l == r)  
	{
		if(r<=6)
		printf("%d\n",tot+1);
	}
	else{
		int mid = l + r >> 1;
		solve(u<<1,l,mid);
		solve(u<<1|1,mid+1,r);
	}
	while(top > lasttop)
	{
		int a = st[top].x,b = st[top].y;
		cut(e[b].x,b+n);cut(e[b].y,b+n);
		link(e[a].x,a+n);link(e[a].y,a+n);
		tot -= e[b].w;
		tot += e[a].w;
		top--;
	}
}
int main()
{
	n = read();
	for(int i = 1;i < n;i++)
	{
		e[i].x = read(),e[i].y = read(),e[i].w = read();
		link(e[i].x,n+i);
		link(e[i].y,n+i);
		tot += e[i].w;
		t[i+n].mx = i + n;
		t[i+n].val = e[i].w;
	}
	m = read();
	for(int i = n;i < m+n;i++)
	{
		e[i].x = read();e[i].y = read();e[i].w = read();
		t[i+n].mx = i+n;
		t[i+n].val = e[i].w;
		int l = read(),r = read();
		update(1,1,32766,l,r,i);
	}
	solve(1,1,32766);
	return 0;
}
2020/7/27 19:28
加载中...