비 오 는 날 꼬리

제목:
n 개의 점 을 가 진 나 무 를 보 여 줍 니 다. m 개의 이벤트 가 있 습 니 다.
매번 x 에서 y 의 경로 에 있 는 모든 점 을 z 의 아 이 템 을 투입 합 니 다.
마지막 으로 점 마다 그 물건 이 가장 많 기 를 바 랍 니 다.
n，m<=100000；
문제 풀이:
데이터 구조 가 좋 은 문제
우선 이 문 제 는 최종 답 을 묻 는 것 이 므 로 모든 사건 을 오프라인 으로 처리한다.
만약 나무 가 하나의 사슬 이 라면 이런 서열 문제 에 대해 어떻게 해 야 하 는 지 고려 해 보 세 요.
왼쪽 점 x 를 z 수량 에 1 을 더 하고 오른쪽 점 y 를 z 수량 - 1 로 설정 합 니 다.
그 다음 에 하나의 가중치 선분 트 리 로 전체 서열 을 쓸 고 최대 치 를 조회 하 는 것 이 답 입 니 다.
시간 복잡 도 O (n + m) logm), 공간 복잡 도 O (mlogm);
매우 우아 한 방법 으로 우 리 는 그것 을 나무 위로 옮 겼 다.
나무의 표 시 는 서열 과 대체적으로 같 습 니 다. 우 리 는 잎 노드 에서 나 무 를 위로 쓸 어 올 립 니 다.
그러면 x, y 결점 표 z 수량 에 1, LCA (x, y), fa (LCA (x, y) 설정 z 수량 - 1;
이것 은 나무 사슬 문제 전환 에 자주 사용 되 는 수단 중의 하나 인 것 같은 데?
그리고 우리 똑 같이 위로 쓸 어...두 시 에 한 뿌리 를 쓸 었 다!
이제 이 두 개의 선분 나 무 를 합 쳐 야 한다.
직접 계발 식 합병 복잡 도가 이상 하 다 면 가중치 선분 수 는 더 좋 은 방법 이 있 습 니 다.
직접 재 귀 합병!
만약 두 나무 에 한 개의 결점 이 없다 면, 바로 결점 이 있 는 것 으로 돌아 가라.
만약 에 결점 이 있 으 면 다시 계산 한 다음 에 계 산 된 새로운 결점 을 되 돌려 주 고 두 개의 오래된 결점 을 회수 합 니 다.
이 복잡 도 는 전체적으로 O (nlogn) 의 것 이다.
다음은 PoPoQQQ 할아버지 의 멋 진 증명 입 니 다. [박수 곰]:
나 는 선분 나무의 세 를 노드 개수 로 정의 했다.
그러면 두 그루 의 선분 나 무 를 합 친 대 가 는 두 그루 의 선분 나무의 세 와 - 새 선분 나무의 세 입 니 다.
그리고 처음에 모든 선분 나무의 세 를 합 친 것 은 O (nlogn) 입 니 다.
한 라인 트 리 에 logn 노드 가 있 습 니 다.
마지막 까지 n 개의 노드 가 있 습 니 다.
그래서 마지막 위치 차 는 O (nlogn) 입 니 다.
일 을 끝 냈 다
그리고 이 문 제 는 시간 공간 이 다 nlogn 이에 요.
복잡 도가 믿 을 만하 다 는 것 을 증명 했다. 그러면 이 문 제 는 실현 되 는 세부 적 인 문 제 를 남 겨 두 었 다.
다른 것 은 별 것 아니 지만, 이 문 제 는 폭발 적 이다!창고 폭발!!!
그리고 넓 은 검색 으로 바 꾸 면 넘 어 갑 니 다.
코드:

#include
#include
#include
#include
#define N 110000
#define MEM 2000000
#define M 1000000000
#define lson l,mid,ls[no]
#define rson mid+1,r,rs[no]
using namespace std;
int fa[N][30],deep[N],size[N],ts[N],ans[N];
int next[N<<2],kind[N<<2],head[N],ce;
bool val[N<<2];
int ma[MEM],kma[MEM],ls[MEM],rs[MEM],root[N],tot;
int mp[MEM],top;
queueq;
int newseg()
{
	if(top)	return mp[top--];
	return ++tot;
}
void delseg(int no)
{
	mp[++top]=no;
	ls[no]=0;
	rs[no]=0;
	ma[no]=0;
}
void Pushup(int no)
{
	if(ma[ls[no]]>=ma[rs[no]])
		ma[no]=ma[ls[no]],kma[no]=kma[ls[no]];
	else
		ma[no]=ma[rs[no]],kma[no]=kma[rs[no]];
}
void update(int l,int r,int &no,int k,int val)
{
	if(!no)	no=newseg();
	if(l==r)
		ma[no]+=val,kma[no]=l;
	else
	{
		int mid=l+r>>1;
		if(k<=mid)	update(lson,k,val);
		else		update(rson,k,val);
		Pushup(no);
	}
	if(!ma[no])
		kma[no]=0;
}
int merge(int l,int r,int nol,int nor)
{
	if(!nol||!nor)	return nol+nor;
	int no=newseg();
	if(l==r)
	{
		ma[no]=ma[nol]+ma[nor];
		kma[no]=l;
	}
	else
	{
		int mid=l+r>>1;
		ls[no]=merge(l,mid,ls[nol],ls[nor]);
		rs[no]=merge(mid+1,r,rs[nol],rs[nor]);
		Pushup(no);
	}
	delseg(nol),delseg(nor);
	return no;
}
namespace Graph
{
	int to[N<<1],next[N<<1],head[N],ce;
	int tq[N],st,en;
	void add(int x,int y)
	{
		to[++ce]=y;
		next[ce]=head[x];
		head[x]=ce;
	}
	void bfs()
	{
		tq[st=en=1]=1;
		int i,x;
		while(st<=en)
		{
			x=tq[st++];
			size[x]=1,deep[x]=deep[fa[x][0]]+1;
			for(i=1;fa[x][i-1];i++)
				fa[x][i]=fa[fa[x][i-1]][i-1];
			for(i=head[x];i;i=next[i])
			{
				if(to[i]!=fa[x][0])
				{
					fa[to[i]][0]=x;
					tq[++en]=to[i];
				}
			}
		}
		while(en)
		{
			size[fa[tq[en]][0]]+=size[tq[en]];
			if(size[tq[en]]==1)
				q.push(tq[en]);
			en--;
		}
	}
};
int LCA(int x,int y)
{
	if(deep[x]=deep[y])
			x=fa[x][k];
		k--;
	}
	if(x==y)	return x;
	k=20;
	while(k>=0)
	{
		if(fa[x][k]!=fa[y][k])
			x=fa[x][k],y=fa[y][k];
		k--;
	}
	return fa[x][0];
}
void Insert(int x,int k,bool v)
{
	val[++ce]=v;
	kind[ce]=k;
	next[ce]=head[x];
	head[x]=ce;
}
int main()
{
	int n,m,i,j,k,l,x,y,z;
	scanf("%d%d",&n,&m);
	for(i=1;i