題解 - $\mathrm{C}\mathrm{F}613\mathrm{D}\mathrm{K}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{s}\mathrm{C}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{e}\mathrm{s}$

• 一道 虛樹+樹形DP好題。

題目意思

戳這里

$\mathrm{S}\mathrm{o}\mathrm{l}$

• 這道題目的重點還是建虛樹，如果不會建立虛樹，虛樹構建學習
• 然后我們就開始愉快地樹形$DP$了
  • 設$f_u$表示以$u$為根節點最少選擇點數
  • 設$g_u$表示以$u$為根節點還沒有處理地特殊點數量
  • 對于轉移：
    • 如果這個點$u$不是特殊點且$g_u>1$，那么就必須選。
    • 如果這個點$u$是特殊點，那么$f_u=(f_u+g_u),g_u=1$，其中$g_u=1$因為還有根節點是特殊點。
    • 對于其他就是：$f_u=\sum f_v,g_u=\sum g_v$
• 對于那些虛樹上的點，如果$u$以及$f{a}_u$都為特殊點，那么輸出$?1$就可以了。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h> using namespace std;inline int read() {int sum=0,ff=1; char ch=getchar();while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}while(isdigit(ch))sum=sum*10+(ch^48),ch=getchar();return sum*ff; }const int N=4e5+5;int n,m,cnt,head[N],siz[N],stak[N]; int ans,in[N],out[N],is[N],p[N],tim; int dep[N],son[N],top[N],f[N],g[N],h[N];struct nood {int nex,to; }; nood e[N*2];inline void jia(int u,int v) {e[++cnt].nex=head[u];head[u]=cnt;e[cnt].to=v; }inline void dfs(int u,int fa) {dep[u]=dep[fa]+1;in[u]=++tim;f[u]=fa;siz[u]=1;for ( int i=head[u];i;i=e[i].nex ){int v=e[i].to;if(v==fa) continue;dfs(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]]) son[u]=v;}out[u]=tim; }inline void dfs2(int u,int tp) {top[u]=tp;if(son[u]) dfs2(son[u],tp);for ( int i=head[u];i;i=e[i].nex ){int v=e[i].to;if(v==f[u]||v==son[u]) continue;dfs2(v,v);} }inline int LCA(int x,int y) {while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);x=f[top[x]];}if(dep[x]>dep[y]) swap(x,y);return x; }inline void dp(int u) {for ( int i=head[u];i;i=e[i].nex ){int v=e[i].to;dp(v);h[u]+=h[v];g[u]+=g[v];}if(is[u]) h[u]+=g[u],g[u]=1;else h[u]+=(g[u]>1),g[u]=(g[u]==1); }inline int calc(int x,int gs) {for ( int i=1;i<=gs;i++ ) if(is[p[i]]&&is[f[p[i]]]) return -1;dp(x);return h[x]; }inline bool cmp(int x,int y) {return in[x]<in[y]; }int main() {n=read();for ( int i=1;i<n;i++ ){int u,v;u=read(),v=read();jia(u,v);jia(v,u);}dfs(1,0);dfs2(1,1);memset(head,0,sizeof(head));cnt=0;int Q=read();for (;Q--;){int gs=read();for ( int i=1;i<=gs;i++ ) is[(p[i]=read())]=1;sort(p+1,p+gs+1,cmp);for ( int i=gs;i>1;i-- ) p[++gs]=LCA(p[i],p[i-1]);sort(p+1,p+gs+1,cmp);gs=unique(p+1,p+gs+1)-p-1;cnt=0;for ( int i=1,top=0;i<=gs;i++ ){while(top&&out[stak[top]]<in[p[i]]) top--;jia(stak[top],p[i]);stak[++top]=p[i];}printf("%d\n",calc(p[1],gs));for ( int i=1;i<=gs;i++ ) head[p[i]]=0,is[p[i]]=0,h[p[i]]=0,g[p[i]]=0;}return 0; }

總結

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

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