网站策划的基本过程,网站设置在哪,建网站 外贸,网页升级紧急通知怎么取消正题 题目大意 nnn个点的一棵树#xff0c;给每个点一个权值是1∼a1\sim a1∼a或−1∼−b-1\sim -b−1∼−b。每次选择正负中一个绝对值最小的删去使得无论如何选择都不会将树分成两个联通块。 解题思路
因为可以随意选择#xff0c;所以aaa和−b-b−b的点一定要连在一起给每个点一个权值是1∼a1\sim a1∼a或−1∼−b-1\sim -b−1∼−b。每次选择正负中一个绝对值最小的删去使得无论如何选择都不会将树分成两个联通块。 解题思路
因为可以随意选择所以aaa和−b-b−b的点一定要连在一起所以我们找到一个位置能将树分为大小aaa和bbb的两部分然后直接对于两部分dfsdfsdfs去赋权就好了。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
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].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa,int z){for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x,z);}dfn[x](cntz);
}
void dfs(int x,int fa){siz[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);siz[x]siz[y];if(flag)return;if(siz[y]A){flag1;dfs(y,x,1);cnt0;dfs(x,y,-1);}else if(siz[y]B){flag1;dfs(y,x,-1);cnt0;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 i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs(1,1);if(flag){for(int i1;in;i)printf(%d\n,dfn[i]);}else printf(-1\n);
}
