自己网站上做淘宝搜索引擎,山东装饰公司网站建设公司,网络营销的特点包含,搜索引擎优化入门正题
题目链接:https://www.luogu.com.cn/problem/P6805 题目大意
给出nnn个点的一棵树#xff0c;qqq次独立的询问。每次询问会在一些节点上新增一些子节点#xff0c;然后你每次可以选择两个为选择过的叶子节点然后覆盖它们的路径#xff0c;要求在覆盖所有边的情况下使…正题
题目链接:https://www.luogu.com.cn/problem/P6805 题目大意
给出nnn个点的一棵树qqq次独立的询问。每次询问会在一些节点上新增一些子节点然后你每次可以选择两个为选择过的叶子节点然后覆盖它们的路径要求在覆盖所有边的情况下使得每次的路径长度和最小。
1≤n,q,∑di≤1051\leq n,q,\sum d_i\leq 10^51≤n,q,∑di≤105 解题思路
先考虑暴力怎么做我们可以把所有叶子去掉然后每个点的权值就是它原来子节点中的叶子数。
然后由于一个节点之间的权值可以两两匹配贪心的话一个节点只有可能有1/21/21/2条路径延伸到父节点这样就可以统计了。
然后考虑多个询问如何处理根据上面的方法每条边只有可能统计1/21/21/2次而统计两次时当且仅当子树内能够两两配对此时因为不能有边没有覆盖所以就只能拆开一个配对分两个上来。
具体地当一个点的子树中叶子数为偶数时它到其父节点的边会被统计两次。
这个用树链剖分维护即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N1];
int n,m,tot,cnt,ls[N],leaf[N],lsz[N];
int dep[N],fa[N],siz[N],son[N],top[N],id[N];
int w[N2],v[N2],lazy[N2];stackint s;
void Downdata(int x){if(!lazy[x])return;lazy[x*2]^1;lazy[x*21]^1;swap(w[x*2],v[x*2]);swap(w[x*21],v[x*21]);lazy[x]0;return;
}
void Build(int x,int L,int R){if(LR){w[x](L1);return;}int mid(LR)1;Build(x*2,L,mid);Build(x*21,mid1,R);w[x]w[x*2]w[x*21];
}
void Change(int x,int L,int R,int l,int r){if(LlRr){swap(w[x],v[x]);lazy[x]^1;return;}int mid(LR)1;Downdata(x);if(rmid)Change(x*2,L,mid,l,r);else if(lmid) Change(x*21,mid1,R,l,r);else Change(x*2,L,mid,l,mid),Change(x*21,mid1,R,mid1,r);w[x]w[x*2]w[x*21];v[x]v[x*2]v[x*21];return;
}
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x){leaf[x](a[ls[x]].next0);siz[x]1;dep[x]dep[fa[x]]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x])continue;fa[y]x;dfs(y);lsz[x]lsz[y];siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}lsz[x]leaf[x];return;
}
void dfs2(int x){id[x]cnt;if(lsz[x]1)Change(1,1,n,cnt,cnt); if(son[x]){top[son[x]]top[x];dfs2(son[x]);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x]||yson[x])continue;top[y]y;dfs2(y);}return;
}
void Updata(int x){while(x){Change(1,1,n,id[top[x]],id[x]);xfa[top[x]];}return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}Build(1,1,n);dfs(1);top[1]1;dfs2(1);while(m--){int k,x,sumlsz[1];scanf(%d,k);for(int i1;ik;i){scanf(%d,x);if(leaf[x]1)leaf[x]2;else sum,Updata(x);s.push(x);}if(sum1)puts(-1);else printf(%d\n,n-1kw[1]);while(!s.empty()){int xs.top();if(leaf[x]2)leaf[x]1;else Updata(x);s.pop();} }return 0;
}
