「HNOI2016」网络 解题报告

「HNOI2016」网络

我有一个绝妙的可持久化树套树思路，可惜的是，它的空间是\(n\log^2 n\)的...

注意到对一个询问，我们可以二分答案

然后统计经过这个点大于当前答案的路径条数，如果这个路径条数等于大于当前答案的所有路径条数，那么这个答案是不行的。

关于链修改单点询问，可以树状数组维护dfs序，然后每次修改链去差分修改

然后把二分答案拿到整体二分上去就可以了

---

Code:

#include <cstdio>

#include <cctype>

#include <cmath>

#include <algorithm>

const int N=3e5+10;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int head[N],to[N<<1],Next[N<<1],cnt;

void add(int u,int v)

{

	to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

int dfn[N],low[N],dep[N],f[18][N],dfsclock;

int n,m,q,s[N],ans[N];

struct koito_yuu{int u,v,x,lca;}yuu[N],yuul[N],yuur[N];

void dfs(int now)

{

	dfn[now]=++dfsclock;

	dep[now]=dep[f[0][now]]+1;

	for(int i=1;f[i-1][now];i++) f[i][now]=f[i-1][f[i-1][now]];

	for(int v,i=head[now];i;i=Next[i])

		if((v=to[i])!=f[0][now])

			f[0][v]=now,dfs(v);

	low[now]=dfsclock;

}

int LCA(int x,int y)

{

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

	for(int i=17;~i;i--)

		if(dep[f[i][x]]>=dep[y])

			x=f[i][x];

	if(x==y) return x;

	for(int i=17;~i;i--)

		if(f[i][x]!=f[i][y])

			x=f[i][x],y=f[i][y];

	return f[0][x];

}

void modify(int x,int d){while(x&&x<=n)s[x]+=d,x+=x&-x;}

int query(int x){int ret=0;while(x)ret+=s[x],x-=x&-x;return ret;}

void modi(int u,int v,int lca,int d)

{

	modify(dfn[u],d);

	modify(dfn[v],d);

	modify(dfn[lca],-d);

	modify(dfn[f[0][lca]],-d);

}

int qry(int u)

{

	return query(low[u])-query(dfn[u]-1);

}

void Divide(int l,int r,int L,int R)

{

	if(l>r) return;

	if(L==R)

	{

		for(int i=l;i<=r;i++)

			if(!yuu[i].v)

				ans[yuu[i].x]=L;

		return;

	}

	int Mid=L+R>>1;

	int lp=0,rp=0,cnt=0;

	for(int i=l;i<=r;i++)

	{

		if(yuu[i].v)

		{

			if(abs(yuu[i].x)>Mid)

			{

				yuur[++rp]=yuu[i];

				if(yuu[i].x>0) modi(yuu[i].u,yuu[i].v,yuu[i].lca,1),++cnt;

				else modi(yuu[i].u,yuu[i].v,yuu[i].lca,-1),--cnt;

			}

			else yuul[++lp]=yuu[i];

		}

		else

		{

			int ct=qry(yuu[i].u);

			if(ct==cnt) yuul[++lp]=yuu[i];

			else yuur[++rp]=yuu[i];

		}

	}

	for(int i=l;i<=r;i++)

		if(yuu[i].v&&abs(yuu[i].x)>Mid)

			modi(yuu[i].u,yuu[i].v,yuu[i].lca,yuu[i].x>0?-1:1);

	for(int i=1;i<=lp;i++) yuu[i+l-1]=yuul[i];

	for(int i=1;i<=rp;i++) yuu[i+l+lp-1]=yuur[i];

	Divide(l,l+lp-1,L,Mid),Divide(l+lp,r,Mid+1,R);

}

int main()

{

	read(n),read(m);

	for(int u,v,i=1;i<n;i++) read(u),read(v),add(u,v),add(v,u);

	dfs(1);

	for(int typ,t,i=1;i<=m;i++)

	{

		read(typ);

		if(typ==0) read(yuu[i].u),read(yuu[i].v),read(yuu[i].x),yuu[i].lca=LCA(yuu[i].u,yuu[i].v);

		else if(typ==1) read(t),yuu[i]=yuu[t],yuu[i].x=-yuu[i].x;

		else read(yuu[i].u),yuu[i].x=++q;

	}

	Divide(1,m,0,(int)(1e9));

	for(int i=1;i<=q;i++) printf("%d\n",ans[i]?ans[i]:-1);

	return 0;

}

---

2019.3.9