南京定制网站建设,做网站公司的未来,wix和wordpress哪个好,佛山市seo广告优化工具正题
P6805 题目大意
给你一棵树#xff0c;每次可选择两个叶子结点#xff0c;然后覆盖路径上的边#xff0c;代价为其长度#xff0c;每个叶子结点只能选一次。
对于每次询问#xff0c;加入若干新点#xff08;只会连接原树的点#xff09;#xff0c;问你覆盖所…正题
P6805 题目大意
给你一棵树每次可选择两个叶子结点然后覆盖路径上的边代价为其长度每个叶子结点只能选一次。
对于每次询问加入若干新点只会连接原树的点问你覆盖所有边的最小代价。 解题思路
因为所有边都要覆盖所以一个点至少连一条到父亲的边
不难发现如果一个点的子树内有偶数各叶子结点那么就要连出两条边否则连一条边因为所有点都要连向父亲所以只计算多出来的
那么可以树链剖分然后用线段树维护子树叶子结点的值
对于每次查询相当于把若干链上的值异或1然后查询整棵树的值 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100100
using namespace std;
int n,m,q,x,y,w,tot,a[N],s[N],h[N],p[N];
int sz[N],fa[N],hs[N],deg[N],low[N],dfn[N],dep[N],top[N],lsz[N];
struct rec
{int to,nx;
}e[N1];
void add(int x,int y)
{e[tot].toy;e[tot].nxh[x];h[x]tot;return;
}
struct Tree
{#define ls x*2#define rs x*21int v[N2],lazy[N2];void push_up(int x){v[x]v[ls]v[rs];return;}void get(int x,int l,int r){lazy[x]^1;v[x]r-l1-v[x];return;}void push_down(int x,int l,int r){if(lazy[x]){int midlr1;get(ls,l,mid);get(rs,mid1,r);lazy[x]0;}return;}void change(int x,int L,int R,int l,int r){if(LlRr){get(x,L,R);return;}push_down(x,L,R);int midLR1;if(rmid)change(ls,L,mid,l,r);else if(lmid)change(rs,mid1,R,l,r);else change(ls,L,mid,l,mid),change(rs,mid1,R,mid1,r);push_up(x);return;}int ask(int x,int L,int R,int l,int r){if(LlRr)return v[x];push_down(x,L,R);int midLR1;if(rmid)return ask(ls,L,mid,l,r);else if(lmid)return ask(rs,mid1,R,l,r);else return ask(ls,L,mid,l,mid)ask(rs,mid1,R,mid1,r);}
}T;
void dfs1(int x)
{sz[x]1;if(deg[x]1)lsz[x]1,p[x]1;for(int ih[x];i;ie[i].nx){int ye[i].to;if(yfa[x])continue;fa[y]x;dep[y]dep[x]1;dfs1(y);sz[x]sz[y];lsz[x]lsz[y];if(sz[y]sz[hs[x]])hs[x]y;}return;
}
void dfs2(int x,int anc)
{dfn[x]w;top[x]anc;if(!(lsz[x]1))T.change(1,1,n,dfn[x],dfn[x]);if(hs[x])dfs2(hs[x],anc);for(int ih[x];i;ie[i].nx){int ye[i].to;if(yfa[x]||yhs[x])continue;dfs2(y,y);}low[x]w;return;
}
void add(int x)
{while(top[x]!1){T.change(1,1,n,dfn[top[x]],dfn[x]);xfa[top[x]];}T.change(1,1,n,dfn[1],dfn[x]);return;
}
int main()
{scanf(%d%d,n,q);for(int i1;in;i){scanf(%d%d,x,y);add(x,y);add(y,x);deg[x];deg[y];}dep[1]fa[1]1;dfs1(1);dfs2(1,1);while(q--){scanf(%d,m);for(int i1;im;i){scanf(%d,a[i]);s[i]1;}a[m1]0;sort(a1,a1m);for(int i1;im;i)if(a[i]a[i1])s[i1]s[i];else if(p[a[i]]){if(!(s[i]1))add(a[i]);//修改一条链}else if(s[i]1)add(a[i]);if(!T.ask(1,1,n,dfn[1],dfn[1]))puts(-1);//无法两两匹配else printf(%d\n,T.ask(1,1,n,dfn[1],low[1])nm-2);//加上没算的边1没有连向父亲的边但两边都会多算一次for(int i1;im;i)if(a[i]!a[i1]){if(p[a[i]]){if(!(s[i]1))add(a[i]);}else if(s[i]1)add(a[i]);}}return 0;
}
