題意
(~~~~) 給出若幹次詢問，每次詢問将對若幹個點增加葉子結點（同一個點可能加多次），定義一組葉子結點比對的權值為這兩點間路徑經過的邊數，求使得比對權值最小且每條邊都至少貢獻過一次的權值。
(~~~~) (1leq nleq 10^5,1leq sum D_i leq 10^5)
本文版權歸 Azazel 與部落格園共有，歡迎轉載，但需保留此聲明，并給出原文位址，謝謝合作。
原文位址：https://www.cnblogs.com/Azazel/p/15192326.html
題解
(~~~~) 首先，葉子結點必須是偶數時才有解，因為奇數時至少會存在一個葉子其到父親的邊不能被清掃。
(~~~~) 接下來考慮一棵子樹：
- 當子樹内葉子結點為奇數時，該子樹根節點到父親的邊會被清掃一次；
- 當子樹内葉子結點為偶數時，該子樹根節點到父親的邊會被清掃兩次；
(~~~~) 是以題解幾乎寫題意裡了屬于是
(~~~~) 考慮證明這個結論的正确性：每個點（除去欽定的根節點）到父親的邊都應該被清掃至少一次。當子樹内隻剩一個葉子結點未比對時，外界也會有奇數個葉子結點供該點比對，偶數同理。當每個點（除去欽定的根節點）到父親的邊都被清掃，我們就可以認為整棵樹被清掃了。
(~~~~) 以上是一個 (mathcal{o(nq)}) 的做法，考慮我們需要的資訊隻有每個點子樹内的葉子結點數量 (mod 2)，故我們用樹剖維護，對于某個點若其為葉子結點則不管，否則将該點到根節點的路徑上所有點的點權 (oplus 1) ，最後統計除了 (1) 之外所有點的點權和。由于 (1) 的點權必定為 (0)，是以統計整棵樹的點權和即可。
代碼
檢視代碼
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,q,m;
int siz[100005],dfn[100005],top[100005],sizLeaf[100005];
int dep[100005],fa[100005],To[100005],Times,son[100005],deg[100005];
bool IsLeaf[100005];
vector <int> G[100005];
void dfs1(int u,int Fa)
{
sizLeaf[u]=IsLeaf[u];fa[u]=Fa;
siz[u]=1;dep[u]=dep[Fa]+1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==Fa) continue;
dfs1(v,u);
siz[u]+=siz[v];sizLeaf[u]=(sizLeaf[u]+sizLeaf[v])%2;
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int T)
{
top[u]=T;dfn[u]=++Times;To[Times]=u;
if(!son[u]) return; dfs2(son[u],T);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
struct SegmentTree{
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
int tr[400005],tag[400005];
void pushUp(int p){tr[p]=tr[ls]+tr[rs];}
void pushDown(int p,int l,int r)
{
if(tag[p])
{
int mid=(l+r)>>1;
tr[ls]=(mid-l+1)-tr[ls];
tr[rs]=(r-mid)-tr[rs];
tag[ls]^=1; tag[rs]^=1;
tag[p]^=1;
}
}
void Build(int p,int l,int r)
{
if(l==r)
{
tr[p]=sizLeaf[To[l]];
return;
}
int mid=(l+r)>>1;
Build(lson); Build(rson);
pushUp(p);
}
void Modify(int p,int l,int r,int lx,int rx)
{
if(lx<=l&&r<=rx)
{
tr[p]=(r-l+1)-tr[p];
tag[p]^=1;
return;
}
int mid=(l+r)>>1;pushDown(p,l,r);
if(lx<=mid) Modify(lson,lx,rx);
if(mid<rx) Modify(rson,lx,rx);
pushUp(p);
}
int Query(int p,int l,int r,int lx,int rx)
{
if(lx<=l&&r<=rx) return tr[p];
int mid=(l+r)>>1,ret=0;pushDown(p,l,r);
if(lx<=mid) ret+=Query(lson,lx,rx);
if(mid<rx) ret+=Query(rson,lx,rx);
return ret;
}
}Seg;
void ModifyPath(int x,int y)
{
// printf("%d %d:",x,y);
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
Seg.Modify(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
Seg.Modify(1,1,n,dfn[x],dfn[y]);
// for(int i=1;i<=n;i++) printf("%d ",Seg.Query(1,1,n,dfn[i],dfn[i]));puts("");
}
vector <int> Changed,V;
int main() {
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=1,x,y;i<n;i++)
{
scanf("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
deg[x]++;deg[y]++;
}
int Sum=0,Tmp;
for(int i=1;i<=n;i++) if(deg[i]==1) IsLeaf[i]=true,Sum++;
dfs1(1,0);dfs2(1,1);
Seg.Build(1,1,n);
// for(int i=1;i<=n;i++) printf("%d ",Seg.Query(1,1,n,dfn[i],dfn[i]));puts("");
Tmp=Sum;
while(q--)
{
Sum=Tmp;
scanf("%d",&m);
for(int i=1,x;i<=m;i++)
{
scanf("%d",&x);
if(IsLeaf[x])
{
Changed.push_back(x);
IsLeaf[x]=false;
continue;
}
V.push_back(x);Sum++;
ModifyPath(x,1);
}
if(Sum&1) puts("-1");
else printf("%d
",((n+m)<<1)-2-(Seg.tr[1])-m);
for(int i=0;i<V.size();i++) ModifyPath(V[i],1);
for(int i=0;i<Changed.size();i++) IsLeaf[Changed[i]]=true;
V.clear();Changed.clear();
}
return 0;
}