南京网站建设 seo,长沙建个网站要多少钱,做茶叶网站的素材,静安建设网站题目大意
给你一棵有 n n n个节点的树#xff0c;并用 01 01 01串告诉你哪些节点上有棋子#xff08;恰好一棵#xff09;。
你可以进行若干次操作#xff0c;每次操作可以将两颗距离至少为 2 2 2的棋子向彼此移动一步。
问能否通过若干次操作使得所有的棋子都在一个点上…题目大意
给你一棵有 n n n个节点的树并用 01 01 01串告诉你哪些节点上有棋子恰好一棵。
你可以进行若干次操作每次操作可以将两颗距离至少为 2 2 2的棋子向彼此移动一步。
问能否通过若干次操作使得所有的棋子都在一个点上。如果能输出最小操作次数否则输出 − 1 -1 −1。 1 ≤ n ≤ 1 0 6 1\leq n\leq 10^6 1≤n≤106
时间限制 2000 m s 2000ms 2000ms空间限制 256 M B 256MB 256MB。 题解
看这道题之前可以先看看AGC034E Complete Compress本题为其加强版。
我们可以枚举最后所有棋子聚集在哪个点设这个点为 r r r我们设 r r r为根。
设 d i s u dis_u disu表示 u u u的子树中每个棋子到 u u u的距离那每一次操作会使 d i s r dis_r disr减少 2 2 2或者不变。我们发现 如果不变的话相当于浪费了一次所以最优的肯定是选择减少 2 2 2。
每次减少 2 2 2要不是在 r r r的一个儿子的 d i s dis dis值减少 2 2 2要不是在 r r r的两个儿子分别减少 1 1 1。我们考虑什么时候无解无解就是子树不能抵消完。设 m n u mn_u mnu表示子树 u u u中的棋子在内部操作若干次直到不能再操作时的 d i s u dis_u disu也就是需要与其他子树操作的最小次数。设 v v v为 u u u的儿子我们比较 m n v s i z v mn_vsiz_v mnvsizv和 d i s u − d i s v − s i z v dis_u-dis_v-siz_v disu−disv−sizv的大小 s i z v siz_v sizv表示子树 v v v中的棋子个数
如果 m n v s i z v ≤ d i s u − d i s v − s i z v mn_vsiz_v\leq dis_u-dis_v-siz_v mnvsizv≤disu−disv−sizv那就是能抵消完最后剩的就是 m n u d i s u % 2 mn_udis_u\%2 mnudisu%2如果 m n v s i z v d i s u − d i s v − s i z v mn_vsiz_vdis_u-dis_v-siz_v mnvsizvdisu−disv−sizv就不能抵消完那我们拿其他部分来抵消 m n v mn_v mnv m n u m n v s i z v − ( d i s u − d i s v − s i z v ) mn_umn_vsiz_v-(dis_u-dis_v-siz_v) mnumnvsizv−(disu−disv−sizv)
我们记录 u u u的所有儿子 v v v的 m n v d i s v 2 s i z v mn_vdis_v2siz_v mnvdisv2sizv的最大值 m x u mx_u mxu然后用这个最大值来与 d i s u dis_u disu作比较即可。
最后看 m n r mn_r mnr是否为 0 0 0。如果为 0 0 0则可以抵消完则用 d i s r / 2 dis_r/2 disr/2来更新答案这里的 d i s r dis_r disr是最开始的 d i s r dis_r disr否则以 r r r为最终聚集的点是无解的。
时间复杂度为 O ( n 2 ) O(n^2) O(n2)。下面考虑优化。
我们可以用换根 D P DP DP。设 s u m u sum_u sumu表示所有棋子到 u u u的距离然后和上面类似地维护 f a d i s u fadis_u fadisu表示以 u u u为根节点除去 u u u的子树部分之外的所有棋子到 u u u的距离 f a m n u famn_u famnu表示以 u u u为根节点时除去 u u u子树部分之外的部分内部操作若干次直到不能再操作时的 d i s u dis_u disu。其实和上面的定义是类似的只不过上面是在 u u u的子树中这里是在 u u u的子树之外。
因为在更新 u u u的儿子 v v v的 f a m n v famn_v famnv时有可能用到自己的 m n v d i s v 2 s i z v mn_vdis_v2siz_v mnvdisv2sizv所以我们在记录 m n v d i s v 2 s i z v mn_vdis_v2siz_v mnvdisv2sizv的最大值时还要记录次大值 m x u , 0 / 1 mx_{u,0/1} mxu,0/1分别表示最大值和次大值。
用与上面类似的方法来维护然后对每个点判断是否有解有解就更新答案。
时间复杂度为 O ( n ) O(n) O(n)。
可以参考代码帮助理解。
code
#includebits/stdc.h
using namespace std;
const int N1000000;
int n,tot0,d[2*N5],l[2*N5],r[N5],dep[N5],siz[N5];
long long ans1e18,dis[N5],mn[N5],fadis[N5],sum[N5],famn[N5],mx[N5][2];
char s[N5];
void add(int xx,int yy){l[tot]r[xx];d[tot]yy;r[xx]tot;
}
void dfs1(int u,int fa){siz[u](s[u]1);for(int ir[u];i;il[i]){int vd[i];if(vfa) continue;dfs1(v,u);siz[u]siz[v];dis[u]dis[v]siz[v];long long tmpdis[v]siz[v]*2mn[v];if(tmpmx[u][0]){mx[u][1]mx[u][0];mx[u][0]tmp;}else if(tmpmx[u][1]) mx[u][1]tmp;}if(mx[u][0]dis[u]) mn[u]dis[u]%2;else mn[u]mx[u][0]-dis[u];
}
void dfs2(int u,int fa){for(int ir[u];i;il[i]){int vd[i];if(d[i]fa) continue;long long nowdis[u]-dis[v]-siz[v];fadis[v]nowsiz[1]-siz[v]fadis[u];sum[v]dis[v]fadis[v];long long famxmx[u][0],fasumsum[u]-dis[v]-siz[v];if(famxdis[v]siz[v]*2mn[v]) famxmx[u][1];famxmax(famx,famn[u]fadis[u]);if(famxfasum) famn[v]fasum%2siz[1]-siz[v];else famn[v]famx-fasumsiz[1]-siz[v];long long mxdmax(mx[v][0],fadis[v]famn[v]);if(mxdsum[v]sum[v]%20) ansmin(ans,sum[v]/2);dfs2(v,u);}
}
int main()
{
// freopen(charlotte.in,r,stdin);
// freopen(charlotte.out,w,stdout);scanf(%d,n);scanf(%s,s1);for(int i1,x,y;in;i){scanf(%d%d,x,y);add(x,y);add(y,x);}dfs1(1,0);if(mn[1]0) ansdis[1]/2;sum[1]dis[1];dfs2(1,0);if(ans1e18) printf(-1\n);else printf(%lld\n,ans);return 0;
}
