正題

題目鏈接:https://www.luogu.com.cn/problem/P6805

---

題目大意

給出$n$個點的一棵樹，$q$次獨立的詢問。每次詢問會在一些節點上新增一些子節點，然后你每次可以選擇兩個為選擇過的葉子節點然后覆蓋它們的路徑，要求在覆蓋所有邊的情況下使得每次的路徑長度和最小。

$1\le n,q,\sum d_i\le 10^5$

---

解題思路

先考慮暴力怎么做，我們可以把所有葉子去掉然后每個點的權值就是它原來子節點中的葉子數。

然后由于一個節點之間的權值可以兩兩匹配，貪心的話一個節點只有可能有$1/2$條路徑延伸到父節點，這樣就可以統計了。

然后考慮多個詢問如何處理，根據上面的方法，每條邊只有可能統計$1/2$次，而統計兩次時當且僅當子樹內能夠兩兩配對，此時因為不能有邊沒有覆蓋，所以就只能拆開一個配對分兩個上來。

具體地當一個點的子樹中葉子數為偶數時它到其父節點的邊會被統計兩次。

這個用樹鏈剖分維護即可。

時間復雜度：$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> using namespace std; const int N=1e5+10; struct node{int to,next; }a[N<<1]; 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[N<<2],v[N<<2],lazy[N<<2];stack<int> s; void Downdata(int x){if(!lazy[x])return;lazy[x*2]^=1;lazy[x*2+1]^=1;swap(w[x*2],v[x*2]);swap(w[x*2+1],v[x*2+1]);lazy[x]=0;return; } void Build(int x,int L,int R){if(L==R){w[x]=(L>1);return;}int mid=(L+R)>>1;Build(x*2,L,mid);Build(x*2+1,mid+1,R);w[x]=w[x*2]+w[x*2+1]; } void Change(int x,int L,int R,int l,int r){if(L==l&&R==r){swap(w[x],v[x]);lazy[x]^=1;return;}int mid=(L+R)>>1;Downdata(x);if(r<=mid)Change(x*2,L,mid,l,r);else if(l>mid) Change(x*2+1,mid+1,R,l,r);else Change(x*2,L,mid,l,mid),Change(x*2+1,mid+1,R,mid+1,r);w[x]=w[x*2]+w[x*2+1];v[x]=v[x*2]+v[x*2+1];return; } void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){leaf[x]=(a[ls[x]].next==0);siz[x]=1;dep[x]=dep[fa[x]]+1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[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 i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x]||y==son[x])continue;top[y]=y;dfs2(y);}return; } void Updata(int x){while(x){Change(1,1,n,id[top[x]],id[x]);x=fa[top[x]];}return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<n;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,sum=lsz[1];scanf("%d",&k);for(int i=1;i<=k;i++){scanf("%d",&x);if(leaf[x]==1)leaf[x]=2;else sum++,Updata(x);s.push(x);}if(sum&1)puts("-1");else printf("%d\n",n-1+k+w[1]);while(!s.empty()){int x=s.top();if(leaf[x]==2)leaf[x]=1;else Updata(x);s.pop();} }return 0; }

總結

以上是生活随笔為你收集整理的P6805-[CEOI2020]春季大扫除【贪心,树链剖分,线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。