遥远的行星? 神奇的国度?

NO,遥远的国度.

这题真皮OVO

考虑换根之后只有两种情况答案会变

一是根与询问点重合 答案整棵树

二是在询问点的子树内,这时候需要……枚举子树树根!

然后用dfs序来判断,这玩意是连续的(嗯……?),而且在每个子树内也是连续的(!)

锁定在哪颗子树内!

if (dfn[child]<=dfn[croot] && dfn[child]+tsize[child]-1>=dfn[croot])

然后你抓着这个子树的根节点把它拎起来,这整棵树其余的部分就耷拉到下面了

然后你就会发现这时候实际是询问这个红色的部分

然后就行了。

画风奇怪??

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;

struct segment_tree { int l,r,w,tag; bool has_tag; } SGT[400010]={0};
struct ed { int pre,to; } edge[200010]={0};
int nodenum,at=1,pointer[100010]={0},fx,tx,nodev[100010]={0},croot;

int anc[100010],topx[100010],tsize[100010],hson[100010],dfn[100010],depth[100010];
int tstamp=0,nnv[100010]={0};
int l[100010][22]={0};

int opt,lx,rx,val,typ,ux,vx;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}
inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline void Fancy(int nownode,int nowdep,int fa)
{
	//LCA
	l[nownode][0]=fa;
	for (int i=1;i<=20;i++) l[nownode][i]=l[l[nownode][i-1]][i-1];
	
	//find heavy son
	depth[nownode]=nowdep; anc[nownode]=fa; tsize[nownode]=1;
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre) if (edge[prex].to!=fa)
	{
		Fancy(edge[prex].to,nowdep+1,nownode);
		tsize[nownode]+=tsize[edge[prex].to];
		if (tsize[edge[prex].to]>tsize[hson[nownode]]) hson[nownode]=edge[prex].to;
	}
}
inline void Dreams(int nownode,int src)
{
	topx[nownode]=src; dfn[nownode]=++tstamp; nnv[tstamp]=nodev[nownode];
	if (hson[nownode]) Dreams(hson[nownode],src);
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre) 
		if (edge[prex].to!=hson[nownode] && edge[prex].to!=anc[nownode]) Dreams(edge[prex].to,edge[prex].to);
}

inline void BuildTree(int lxx,int rxx,int inx)
{
	SGT[inx].l=lxx; SGT[inx].r=rxx;
	if (lxx==rxx) { SGT[inx].w=nnv[lxx]; return; }
	int mid=(lxx+rxx)>>1;
	BuildTree(lxx,mid,inx<<1);
	BuildTree(mid+1,rxx,inx<<1|1);
	SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w);
}
inline void pushdown(int inx)
{
	SGT[inx<<1].tag=SGT[inx<<1|1].tag=SGT[inx].tag;
	SGT[inx<<1].has_tag=SGT[inx<<1|1].has_tag=true;
	SGT[inx<<1].w=SGT[inx<<1|1].w=SGT[inx].tag;
	SGT[inx].tag=0; SGT[inx].has_tag=false;
}
inline void update(int inx)
{
	if (SGT[inx].l>=lx && SGT[inx].r<=rx)
	{
		SGT[inx].w=val; SGT[inx].tag=val; SGT[inx].has_tag=true;
		return;
	}
	if (SGT[inx].has_tag) pushdown(inx);
	int mid=(SGT[inx].l+SGT[inx].r)>>1;
	if (lx<=mid) update(inx<<1);
	if (rx>mid) update(inx<<1|1);
	SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w);
}
inline int query(int inx)
{
	if (SGT[inx].l>=lx && SGT[inx].r<=rx) return SGT[inx].w;
	if (SGT[inx].has_tag) pushdown(inx);
	int mid=(SGT[inx].l+SGT[inx].r)>>1,ret=2*1e9;
	if (lx<=mid) ret=query(inx<<1);
	if (rx>mid) ret=min(ret,query(inx<<1|1));
	SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w);
	return ret;
}

inline int LCA(int u,int v)
{
	if (depth[u]<depth[v]) swap(u,v);
	for (int i=20;i>=0;i--) if (depth[l[u][i]]>=depth[v]) u=l[u][i];
	if (u==v) return u;
	for (int i=20;i>=0;i--) if (l[u][i]!=l[v][i]) { u=l[u][i]; v=l[v][i]; }
	return anc[u];
}

inline void upd_range(int u,int v)
{
	while (topx[u]!=topx[v])
	{
		if (depth[topx[u]]<depth[topx[v]]) swap(u,v);
		lx=dfn[topx[u]]; rx=dfn[u]; update(1);
		u=anc[topx[u]];
	}
	if (depth[u]<depth[v]) swap(u,v);
	lx=dfn[v]; rx=dfn[u]; update(1);
}
inline int solve(int u)
{
	if (u==croot) { lx=1; rx=tstamp; return query(1); }
	else if (LCA(croot,u)!=u)
	{
		lx=dfn[u]; rx=dfn[u]+tsize[u]-1;
		return query(1);
	}
	else
	{
		int ret=2*1e9;
		for (int prex=pointer[u];prex;prex=edge[prex].pre) if (edge[prex].to!=anc[u])
		{
			if (dfn[edge[prex].to]<=dfn[croot] && dfn[edge[prex].to]+tsize[edge[prex].to]-1>=dfn[croot])
			{
				lx=1; rx=dfn[edge[prex].to]-1;
				if (rx>=lx) ret=min(ret,query(1));
				lx=dfn[edge[prex].to]+tsize[edge[prex].to]; rx=tstamp;
				if (rx>=lx) ret=min(ret,query(1));
			}
		}
		return ret;
	}
}

int main()
{
	readx(nodenum); readx(opt);
	for (int i=1;i<nodenum;i++)
	{
		readx(fx); readx(tx); 
		Insert();
	}
	for (int i=1;i<=nodenum;i++) readx(nodev[i]);
	readx(croot);
	
	Fancy(1,1,0); Dreams(1,1);
	BuildTree(1,tstamp,1);

	for (int i=1;i<=opt;i++)
	{
		readx(typ);
		if (typ==1) readx(croot);
		else if (typ==2)
		{
			readx(ux); readx(vx); readx(val);
			upd_range(ux,vx);
		}
		else { readx(ux); printf("%d\n",solve(ux)); }
	}
	return 0;
}

 

分类: 树剖

发表评论

电子邮件地址不会被公开。 必填项已用*标注