正题

---

题目大意

$n$个点的一棵树，给每个点一个权值是$1\sim a$或$-1\sim -b$。每次选择正负中一个绝对值最小的删去使得无论如何选择都不会将树分成两个联通块。

---

解题思路

因为可以随意选择，所以$a$和$-b$的点一定要连在一起，所以我们找到一个位置能将树分为大小$a$和$b$的两部分，然后直接对于两部分$dfs$去赋权就好了。

时间复杂度$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"); }

总结

以上是生活随笔为你收集整理的jzoj6803-NOIP2020.9.26模拟tom【构造】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。