題目描述：

luogu

cf

題解：

虛樹上dp。

建虛樹沒啥說的。

那么dp狀態？

考慮dfs時返回一個值，代表這個子樹上面需不需要隔斷。

如果當前點可以占，那么有至少兩個這種子樹時應該選這個點并返回0，要不然返回1；

如果不能占，直接加到dp值上，然后返回1即可。

代碼：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 100050; template<typename T> inline void read(T&x) {T f = 1,c = 0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}x = f*c; } int n,Q,hed[N],cnt,Hed[N],Cnt; struct EG {int to,nxt; }e[N<<1],E[N]; void ae(int f,int t) {e[++cnt].to = t;e[cnt].nxt = hed[f];hed[f] = cnt; } void aE(int f,int t) {E[++Cnt].to = t;E[Cnt].nxt = Hed[f];Hed[f] = Cnt; } int sta[N],tl,Sta[N],Tl,rt,k[N]; bool vis[N],use[N]; int dep[N],tin[N],siz[N],son[N],tout[N],fa[N],tim,top[N]; bool cmp(int x,int y){return tin[x]<tin[y];} bool fs(int x,int y){return tin[x]<tin[y]&&tout[x]>=tout[y];} void dfs1(int u,int f) {fa[u] = f,siz[u] = 1,dep[u] = dep[f]+1;for(int j=hed[u],to;j;j=e[j].nxt)if((to=e[j].to)!=f){dfs1(to,u);siz[u]+=siz[to];if(siz[son[u]]<siz[to])son[u]=to;} } void dfs2(int u,int Top) {top[u] = Top,tin[u] = ++tim;if(son[u])dfs2(son[u],Top);for(int j=hed[u],to;j;j=e[j].nxt)if((to=e[j].to)!=fa[u]&&to!=son[u])dfs2(to,to);tout[u] = tim; } int get_lca(int x,int y) {while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x = fa[top[x]];}return dep[x]<dep[y]?x:y; } int dp[N]; int dfs(int u) {int tmp = 0;for(int j=Hed[u],to;j;j=E[j].nxt){to = E[j].to;tmp+=dfs(to);dp[u]+=dp[to];}if(!use[u]){if(tmp>1)dp[u]++,tmp=0;}else dp[u]+=tmp,tmp=1;return tmp; } void clear() {for(int i=1,u;i<=tl;i++){u = sta[i];vis[u]=use[u]=0;Hed[u]=dp[u]=0;}tl=Tl=Cnt=0; } int main() { // freopen("tt.in","r",stdin); read(n);for(int u,v,i=1;i<n;i++){read(u),read(v);ae(u,v),ae(v,u);}dfs1(1,0),dfs2(1,1);read(Q);for(int m,i=1;i<=Q;i++){read(m);tl = m;for(int j=1,x;j<=m;j++)read(x),vis[x]=use[x]=1,sta[j]=x;sort(sta+1,sta+1+m,cmp);for(int j=1,x;j<m;j++)if(!vis[x=get_lca(sta[j],sta[j+1])])vis[x]=1,sta[++tl]=x;sort(sta+1,sta+1+tl,cmp);rt = sta[1];Sta[Tl=1]=rt;bool FG = 0;for(int j=2;j<=tl;j++){while(Tl&&!fs(Sta[Tl],sta[j]))Tl--;Sta[++Tl] = sta[j];if(fa[sta[j]]==Sta[Tl-1]&&use[Sta[Tl-1]]&&use[sta[j]])FG=1;aE(Sta[Tl-1],sta[j]);}if(FG){puts("-1");}else{dfs(rt);printf("%d\n",dp[rt]);}clear();}return 0; } View Code

?

轉載于:https://www.cnblogs.com/LiGuanlin1124/p/11147871.html

總結

以上是生活随笔為你收集整理的CF613D Kingdom and its Cities的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。