网站开发需要什么知识,留言网站模板,手机建网站挣钱吗,全自动网页制作正题
题目链接:https://www.luogu.com.cn/problem/AT4995 题目大意 nnn个点的一棵树#xff0c;上面有一些棋子#xff0c;每次可以选择两个棋子移动到他们之间的路径上相邻的点上#xff0c;求最少多少步能移动到一个点上。 n∈[1,2000]n\in[1,2000]n∈[1,2000] 解题思路 …正题
题目链接:https://www.luogu.com.cn/problem/AT4995 题目大意
nnn个点的一棵树上面有一些棋子每次可以选择两个棋子移动到他们之间的路径上相邻的点上求最少多少步能移动到一个点上。
n∈[1,2000]n\in[1,2000]n∈[1,2000] 解题思路
如果固定最终节点的话这个节点rtrtrt可行的话那么答案一定是∑dis(rt,x)2\frac{\sum dis(rt,x)}{2}2∑dis(rt,x)。
那么现在就转变为一个判定性问题我们现在的操作变为了每次选择两个没有祖先关系的点然后将它们往它们的LCALCALCA处移动一格。
同样的我们发现如果我们在处理一个点xxx作为LCALCALCA时我只会关心所有节点来自它的哪个儿子而不用考虑具体的位置。所以可以搞树形dpdpdp。
设fxf_xfx表示xxx的子树内最多的移动次数定义sx∑y∈subtree(x)dis(x,y)s_x\sum_{y\in subtree(x)}dis(x,y)sx∑y∈subtree(x)dis(x,y)的话那么我们的转移和max{sy}(x−y)max\{s_y\}(x-y)max{sy}(x−y)有关。
若max{sy}×2≤sxmax\{s_y\}\times 2\leq s_xmax{sy}×2≤sx那么这里面的节点可以两两配对fxsx2f_x\frac{s_x}{2}fx2sx。
否则他sss最大的子树yyy之中会有剩余的节点无法相互匹配那么有fxsx−symin{fy,sy−⌊sx2⌋}f_xs_x-s_ymin\{f_y,s_y-\lfloor\frac{s_x}{2}\rfloor\}fxsx−symin{fy,sy−⌊2sx⌋}
然后如果fxsx2f_x\frac{s_x}{2}fx2sx那么xxx就是可行的答案
时间复杂度O(n2)O(n^2)O(n2) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2100;
struct node{int to,next;
}a[N1];
int n,tot,ls[N],s[N],w[N],f[N],ans;
char v[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dp(int x,int fa){s[x]w[x]0;int mx0,son0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dp(y,x);w[x]w[y];s[x]s[y]w[y];if(s[y]w[y]mx)mxs[y]w[y],sony;}if(mx*2s[x])f[x]s[x]-mxmin(f[son],mx-s[x]/2);else f[x]s[x]/2;w[x](v[x]1);return;
}
int main()
{scanf(%d,n);scanf(%s,v1);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}ans1e9;for(int i1;in;i){dp(i,i);if(s[i]1)continue;if(f[i]s[i]/2)ansmin(ans,f[i]);}if(ans1e9)puts(-1);else printf(%d\n,ans);return 0;
}
