正題

---

題目大意

$n$個(gè)點(diǎn)的一棵樹，給每個(gè)點(diǎn)一個(gè)權(quán)值是$1～a$或$?1～?b$。每次選擇正負(fù)中一個(gè)絕對(duì)值最小的刪去使得無論如何選擇都不會(huì)將樹分成兩個(gè)聯(lián)通塊。

---

解題思路

因?yàn)榭梢噪S意選擇，所以$a$和$?b$的點(diǎn)一定要連在一起，所以我們找到一個(gè)位置能將樹分為大小$a$和$b$的兩部分，然后直接對(duì)于兩部分$dfs$去賦權(quán)就好了。

時(shí)間復(fù)雜度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; struct node{int to,next; }a[N*2]; int n,A,B,tot,cnt,ls[N],siz[N],dfn[N]; bool flag; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int fa,int z){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x,z);}dfn[x]=(cnt+=z); } void dfs(int x,int fa){siz[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x);siz[x]+=siz[y];if(flag)return;if(siz[y]==A){flag=1;dfs(y,x,1);cnt=0;dfs(x,y,-1);}else if(siz[y]==B){flag=1;dfs(y,x,-1);cnt=0;dfs(x,y,1);}}return; } int main() {freopen("tom.in","r",stdin);freopen("tom.out","w",stdout);scanf("%d%d%d",&n,&A,&B);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}dfs(1,1);if(flag){for(int i=1;i<=n;i++)printf("%d\n",dfn[i]);}else printf("-1\n"); }

總結(jié)

以上是生活随笔為你收集整理的jzoj6803-NOIP2020.9.26模拟tom【构造】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。