[USACO18JAN][luoguP4183 ]Cow at Large P

前言

这是一道考试题
需要一定的idea
构造好后似乎就是裸的点分治了

题目相关

题目链接

题目大意

这个大意写的很烦，不如看题面
有一棵$n$个点的树
设定一个动点：其每秒可以走到树上相邻的一个节点，若当前它在一个度数为1的节点上，它可以逃出这棵树
定义动点相遇为它们在节点上或边上相遇
对于每个点，求现在在当前点上有个动点想要逃出这棵树，你至少要在多少个叶子节点上放置防守动点才能保证它不会逃出去（如果防守动点碰到动点，那么那个动点就被抓住了）

数据范围

n≤7∗104n\le7*10^4n≤7∗104

题解

我们可以通过$\Theta (n)$的树形dp求出离$i$点最近的叶子节点到$i$点的距离gig_igi​
可能算上下dp
设$i$号点的度数为did_idi​
我们发现对于di=1d_i=1di​=1的点答案一定为$1$（即放一个点在它自己上即可）
那么我们考虑如何统计di≠1d_i\neq1di​̸​=1的点
对于每一个根（即选中的那个点），设depidep_idepi​为根到$i$点的距离，faifa_ifai​为$i$号点的父亲
每当有一个节点$i$满足depi≥gidep_i\ge g_idepi​≥gi​并且depfai<gfaidep_{fa_i}<g_{fa_i}depfai​​<gfai​​，那么当前根的答案加一
然后这个统计大概是Θ(n2)\Theta(n^2)Θ(n2)的
然后考虑优化
我们发现对于depi≥gidep_i\ge g_idepi​≥gi​的节点的存在都在联通子树中
每个联通子树贡献$1$的答案（树根贡献）
如果我们可以快速计数就可以获取答案
然后这个时候有一个很巧妙的构造
考场上我并没有想到这个
对于一个$m$个点的子树，其边数是$m-1$条
我们发现对于这个子树∑di=2∗(m−1)+1\sum d_i=2*(m-1)+1∑di​=2∗(m−1)+1
我们又发现$$\sum 1=m$$
所以∑di=2∗(m−1)+1∑di=2∗m−11=2∗m−∑di1=∑(2−di)\begin{aligned} \sum d_i&=2*(m-1)+1\\ \sum d_i&=2*m-1\\ 1&=2*m-\sum d_i\\ 1&=\sum(2-d_i) \end{aligned}∑di​∑di​11​=2∗(m−1)+1=2∗m−1=2∗m−∑di​=∑(2−di​)​
刚好符合我们想要的
所以我们现在要求的就是：∑i=1n[depi≥gi](2−di)\sum_{i=1}^n[dep_i\ge g_i](2-d_i)i=1∑n​[depi​≥gi​](2−di​)
我们发现∑i=1n(2−di)=∑i=1n2−∑i=1ndi=2∗n−2∗(n−1)=2\begin{aligned} \sum_{i=1}^n(2-d_i)&=\sum_{i=1}^n2-\sum_{i=1}^nd_i\\ &=2*n-2*(n-1)\\ &=2 \end{aligned}i=1∑n​(2−di​)​=i=1∑n​2−i=1∑n​di​=2∗n−2∗(n−1)=2​
然后我们要求的就成了2−∑i=1n[depi<gi](2−di)2-\sum_{i=1}^n[dep_i<g_i](2-d_i)2−i=1∑n​[depi​<gi​](2−di​)
设点$u$的答案为ansuans_uansu​
ansu=2−∑v=1n[dis(u,v)<gv](2−dv)ans_u=2-\sum_{v=1}^n[dis(u,v)<g_v](2-d_v)ansu​=2−v=1∑n​[dis(u,v)<gv​](2−dv​)
然后就可以使用点分治
我们点分的时候每次计算经过当前分治重心的路径点对$(u,v)$
设点$i$与分治重心的距离为pip_ipi​
dis(u,v)=pu+pvdis(u,v)=p_u+p_vdis(u,v)=pu​+pv​
然后
dis(u,v)<gv⇔pu+pv<gv⇔pu<gv−pvdis(u,v)<g_v\Leftrightarrow p_u+p_v<g_v\Leftrightarrow p_u<g_v-p_vdis(u,v)<gv​⇔pu​+pv​<gv​⇔pu​<gv​−pv​
用树状数组维护即可
复杂度Θ(nlog2n)\Theta(nlog^2n)Θ(nlog2n)

代码

贴上AC代码

#include
#include
#include
#include
namespace fast_IO
{const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long LL;
#define rg register
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;}
template <typename T> inline void swap(T*a,T*b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;  
}
template <typename T> void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
const int maxn=70001,maxm=140002,INF=0x7f7f7f7f;
int n,d[maxn];
int head[maxn],nxt[maxm],tow[maxm],tmp=1;
int fi[maxn];
inline void addb(const int u,const int v)
{tmp++;nxt[tmp]=head[u];head[u]=tmp;tow[tmp]=v;
}
void dfs1(const int  u,const int fa)
{for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;dfs1(v,u);mind(fi[u],fi[v]+1);}if(fi[u]==INF)fi[u]=0;
}
void dfs2(const int  u,const int fa)
{for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;mind(fi[v],fi[u]+1);dfs2(v,u);}
}
bool Hash[maxn];int son[maxn],minn,root,size;
int ans[maxn];
void getroot(const int u,const int fa)
{son[u]=1;int maxx=0;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa||Hash[v])continue;getroot(v,u);son[u]+=son[v];maxd(maxx,son[v]);}maxd(maxx,size-son[u]);if(maxx<minn)minn=maxx,root=u;
}
int Q[maxn],tot,dis[maxn];
void dfs(const int u,const int fa)
{Q[++tot]=u; for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa||Hash[v])continue;dis[v]=dis[u]+1,dfs(v,u);}
}
int tree[maxn];
inline int lowbit(const int x){return x&-x;}
inline void add(int whe,const int man)
{while(whe<=n){tree[whe]+=man;whe+=lowbit(whe);}
}
inline int qz(int whe)
{rg int res=0;while(whe){res+=tree[whe];whe^=lowbit(whe);}return res;
}
void calc(const int u,const int sign,const int G)
{tot=0,dis[u]=G;dfs(u,u);for(rg int i=1;i<=tot;i++){const int v=Q[i];add(n-fi[v]+dis[v],2-d[v]);}for(rg int i=1;i<=tot;i++){const int v=Q[i];ans[v]+=sign*qz(n-dis[v]-1);}for(rg int i=1;i<=tot;i++){const int v=Q[i];add(n-fi[v]+dis[v],d[v]-2);}
}
void solve(const int u,const int SIZE,const int SON)
{Hash[u]=1;calc(u,-1,0);for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(Hash[v])continue;calc(v,1,1);minn=INF,size=son[v];if(size>SON)size=SIZE-SON;getroot(v,u),solve(root,size,son[root]);}
}
int main()
{memset(fi,0x7f,sizeof(fi));read(n);for(rg int i=1;i<n;i++){int u,v;read(u),read(v);addb(u,v),addb(v,u);d[u]++,d[v]++;}int RT=0;for(rg int i=1;i<=n;i++)if(d[i]>1)RT=i;dfs1(RT,RT);dfs2(RT,RT);for(rg int i=1;i<=n;i++)ans[i]=2;minn=INF,size=n,getroot(1,1),solve(root,size,son[root]);for(rg int i=1;i<=n;i++)print(d[i]==1?1:ans[i]),putchar('\n');return flush(),0;
}

总结

构造很巧妙，一个很好的idea
然后点分治比较裸，很清真

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！