[省选集训2022] 模拟赛11

定位系统

题目描述

\(n\) 个城市构成一棵树，现在要求在一些城市中设置监测点，使得每个城市可以通过到监测点的距离区分出来（不同可以知道是到哪个监测点的距离，可以类比为树上的坐标）

给定 \(q\) 次修改，每次断开边 \((u,v)\) 再连上边 \((x,y)\)，然后求出最小设置的监测点数目。

解法

无根树问题考虑定根，我们先枚举根强制根选取，那么只有深度相同的点需要区分。设 \(f(x)\) 表示子树 \(x\) 内设置关键点的数目，如果 \(x\) 有多个子树，我们可能要在合并的时候多设置关键点才能区分子树，显然要求是至多一个子树内没有关键点：

\[f(x)=\sum_{y\in son_x} \max(f(y),1)-[\prod_{y\in son_x} f(y)=0] \]

接下来就是定根的问题了，一定要去找结论（~~我就是凭感觉找错了结论~~），考虑我们添加关键点的过程都是必要的，那么如果根是度数 \(\geq 3\) 的点，那么根是不需要选取的，并且由于其他点的选取是必要的，我们得到了最优解。

然后考虑这个修改显然就是让你写 \(\tt lct\) 维护 \(\tt ddp\) 了，这题一个很强的操作是维护分段函数。

具体来说就是自变量 \(=0\)，那么对应函数 \(A\)（一次项系数为 \(0\)）；自变量 \(>0\) 又对应着函数 \(B\)（一次项系数为 \(1\)），那么函数如何合并呢？考虑两个分段函数 \(u,v\) 按顺序合并，我们把 \(v_A\) 带入 \(u\) 的分段函数中得到新的 \(A\)，由于 \(f\) 是单调的，所以大于 \(0\) 之后不会再变回 \(0\)，那么新的 \(B\) 就是 \(u_B+v_B\) 了。

但是本题由于要定根所以还要写 makeroot，所以你需要维护正序和逆序的函数。

此外注意重链底端的函数是没有定义的，所以只能直接拿值，那么我们在求某个重链的值时，把最低点 splay 到根，然后把判断是否有左儿子，如果有则带值进左儿子的函数，如果没有则用轻儿子的信息计算。

#include 
#include 
#include 
#include 
using namespace std;
const int M = 500005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
void write(int x)
{
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int n,d[M],ch[M][2],fa[M],sum[M],num[M],st[M],fl[M];
multiset> s;
struct node
{
	int a,b;
	node(int A=0,int B=0) : a(A) , b(B) {}
	int get(const int &x) const {return !x?b:x+a;}
	node operator & (const node &r) const
		{return node(a+r.a,get(r.b));}
}l[M],r[M];
void up(int x)
{
	if(!x) return ;
	l[x]=r[x]=node(sum[x]-(num[x]>0),sum[x]);
	if(ch[x][0])
	{
		l[x]=l[ch[x][0]]&l[x];
		r[x]=r[x]&r[ch[x][0]];
	}
	if(ch[x][1])
	{
		l[x]=l[x]&l[ch[x][1]];
		r[x]=r[ch[x][1]]&r[x];
	}
}
void flip(int x)
{
	if(!x) return ;
	swap(l[x],r[x]);fl[x]^=1;
	swap(ch[x][0],ch[x][1]);
}
void down(int x)
{
	if(!x || !fl[x]) return ;
	flip(ch[x][0]);
	flip(ch[x][1]);
	fl[x]=0;
}
int nrt(int x)
{
	return ch[fa[x]][0]==x || ch[fa[x]][1]==x;
}
int chk(int x)
{
	return ch[fa[x]][1]==x;
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
	ch[y][k]=w;fa[w]=y;
	if(nrt(y)) ch[z][chk(y)]=x;fa[x]=z;
	ch[x][k^1]=y;fa[y]=x;
	up(y);up(x);
}
void splay(int x,int tar=0)
{
	if(!x) return ;
	int y=x,z=0;st[++z]=x;
	while(nrt(y)) st[++z]=y=fa[y];
	while(z) down(st[z--]);
	while(nrt(x) && fa[x]!=tar)
	{
		int y=fa[x];
		if(nrt(y) && fa[y]!=tar)
		{
			if(chk(x)==chk(y)) rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
}
int calc(int x,int fa=0)
{
	splay(x,fa);
	while(ch[x][1]) down(x),x=ch[x][1];
	splay(x,fa);
	int t=sum[x]-(num[x]>0);
	if(!ch[x][0]) return t;
	return l[ch[x][0]].get(t);
}
void access(int x)
{
	for(int y=0,tmp=0;x;x=fa[y=x])
	{
		splay(x);
		if(ch[x][1])
		{
			tmp=calc(ch[x][1],x);
			sum[x]+=max(1,tmp);num[x]+=!tmp;
		}
		if(y)
		{
			tmp=calc(y);
			sum[x]-=max(1,tmp);num[x]-=!tmp;
		}
		splay(y);ch[x][1]=y;up(x);
	}
}
void makert(int x)
{
	access(x);splay(x);flip(x);
}
void cut(int x,int y)
{
	makert(x);access(y);
	splay(x);splay(y,x);
	ch[x][1]=fa[y]=0;up(x);
}
void link(int x,int y)
{
	makert(x);access(y);splay(y);
	fa[x]=y;ch[y][1]=x;up(y);
}
void add(int x) {s.insert(make_pair(d[x],x));}
void rem(int x) {s.erase(make_pair(d[x],x));}
void print()
{
	if(n==1) puts("0");
	else if(s.rbegin()->first<=2) puts("1");
	else
	{
		int x=s.rbegin()->second;
		makert(x);printf("%d\n",calc(x));
	}
}
signed main()
{
	freopen("location.in","r",stdin);
	freopen("location.out","w",stdout);
	n=read();
	for(int i=1;i


						
							

						
							
							
			数据结构-LCTDP-动态DP

[省选集训2022] 模拟赛11

定位系统

相关

标签