[USACO18JAN]Cow at Large P

Description:

贝茜被农民们逼进了一个偏僻的农场。农场可视为一棵有 $N$ 个结点的树，结点分别编号为 $1,2,\ldots, N$ 。每个叶子结点都是出入口。开始时，每个出入口都可以放一个农民（也可以不放）。每个时刻，贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了（在边上或点上均算），则贝茜将被抓住。抓捕过程中，农民们与贝茜均知道对方在哪个结点。

Hint:

$n \le 7*10^4$

Solution:

很有趣的题

题解大多是点分治做法

但是由于我的点分治太菜

便学习了这种神仙做法,还跑到了$luogu$ $rk5$?

设牛在rt处出发,现在处于u,并且有叶子v

不难发现我们需要预处理出每个点到它最近叶子节点的距离

然后根据 $dep[rt]-dep[u] \le dep[u]-dep[v] $

来判断这个叶子是否可以放农民来控制它

如果可以,则return,因为越早控制住这个点,答案就越小

首先,显然一条链上的答案都是相等的

所有考虑把链缩成边,再暴力每个点$dfs$

这样复杂度就会降下来,不过貌似会被菊花图卡飞?

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ls p<<1

#define rs p<<1|1

using namespace std;

typedef long long ll;

const  int mxn=7e4+5;

int n,tot,cnt,ans,x,y,w,f[mxn],in[mxn],hd[mxn];

inline int read() {

	char c=getchar(); int x=0,f=1;

	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}

	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

	return x*f;

}

inline void chkmax(register int &x,register int y) {if(x<y) x=y;}

inline void chkmin(register int &x,register int y) {if(x>y) x=y;}

queue< int > q;

 int ev;

struct ed {

	int to,nxt,go,w,fa;

}t[mxn<<1];

inline void add(register int u,register int v) {

	t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;

}

void bfs()

{

	for(register int i=1;i<=n;++i)

		if(in[i]==1) q.push(i),f[i]=0;

		else f[i]=-1;

	while(!q.empty()) {

		register int u=q.front(); q.pop();

		for(register int i=hd[u];i;i=t[i].nxt) {

			register int v=t[i].to;

			if(f[v]==-1) {

				f[v]=f[u]+1;

				q.push(v);

			}

		}

	}

} //使用广搜巧妙地处理f数组

void dfs1(register int u,register int fa,register int d) {

	if(fa&&in[u]!=2) {x=u,ev=fa,w=d;return ;} //对于每个点只处理它周围的链,保证复杂度

	for(register int i=hd[u];i;i=t[i].nxt) {

		register int v=t[i].to;

		if(v==fa) continue ;

		dfs1(v,u,d+1);

		t[i].go=x,t[i].fa=ev,t[i].w=w-d; //缩边,细节稍多

	}

}

void dfs2(register int u,register int fa,register int d)

{

	if(f[u]<=d) {

		++ans;

		return ;

	}

	for(register int i=hd[u];i;i=t[i].nxt) {

		if(t[i].to!=fa)

		dfs2(t[i].go,t[i].fa,d+t[i].w); //在新图上算答案

	}

}

int main()

{

	n=read(); register int u,v;

	for(register int i=1;i<n;++i) {

		u=read(); v=read();

		add(u,v); add(v,u);

		++in[u]; ++in[v];

	}

	bfs();

	for(register int i=1;i<=n;++i)

		if(in[i]!=2) {dfs1(i,0,0);}

	for(register int i=1;i<=n;++i) {

		if(in[i]==1) {

			puts("1");

			continue ;

		}

		ans=0; dfs2(i,0,0);

		printf("%d\n",ans);

	}

    return 0;

}

巴特西

[USACO18JAN]Cow at Large P

Description:

Hint:

Solution:

最新文章

热门文章