crazy_cloud's Blog
0%

HDU5511 Minimum Cut-Cut

Posted on Edited on In

题目大意

给定一颗 \(n\) 个节点的无根树，除此之外还给定一些非树边 \((x,y)\)。 这些非树边比较特殊，它们满足将树看成 \(1\) 为根的有根树的时候，\(\mathrm{lca}(x,y)=1\)。 树边和非树边的数量之和是 \(m\)。 要求求出恰好删除两条树边的一个最小的割。

\(3\leq n\leq 2\times10^4,n-1\leq m\leq 10^5\)

题目分析

考虑两种情况：一种是割了两条存在祖先儿子关系的树边，一种是割了两条没有祖先儿子关系的树边。（似乎这题不能够割掉一个叶子节点所有边让叶子孤立出来？我也不明白……） 我们令 \(d_x\) 表示一个端点落在 \(x\) 的子树内的所有非树边条数。

对于第一种情况，假设删的是 \((x,\mathrm{fa}_x)\), \((y,\mathrm{fa}_y)\)（\(x\) 是 \(y\) 的祖先）那么答案就是 \(d_x-d_y\)，\(x\) 固定时 \(y\) 取 \(x\) 的儿子显然最优，直接枚举即可。

对于第二种情况，我们令 \(\mathrm{cnt}_{x,y}\) 表示一个端点在 \(x\) 子树内，一个在 \(y\) 子树内的边的数量，那么显然答案是 \(d_x+d_y-2\mathrm{cnt}_{x,y}\)。

考虑在 \(\mathrm{DFS}\) 的过程中使用数据结构来实时维护对于当前 \(\mathrm{DFS}\) 到的点 \(x\) 而言，每一个点 \(y\) 的 \(d_y-2\mathrm{cnt}_{x,y}\)。这个怎么实现呢？考虑使用重链剖分+标记不下传的动态开点的线段树，我们合并各个子树的线段树，当前新加入的相当于给某一条树链打上 tag。

这样搞的话时空复杂度都是 \(O(m\log^2n)\) 的，可是这题空间比较紧过不了。怎么办呢？我们考虑使用一个很 tricky 的技巧：我们重链剖分了这一棵树，那么我们 \(\mathrm{DFS}\) 的时候先进入重儿子，然后直接继承重儿子的线段树，对于轻儿子我们线段树合并的同时回收空闲节点。这样我们 \(\mathrm{DFS}\) 到点 \(x\) 的时候需要的线段树个数就是 \(x\) 到根路径上的轻边条数，而且每一棵线段树最多只会有 \(O(n)\) 个节点。因此空间复杂度是 \(O(n\log n)\)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <queue>

using namespace std;

int read()
{
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}

const int N=20005;
const int E=N<<1;
const int M=100005;
const int M_=M<<1;
const int LGN=16;
const int S=(N<<2)*LGN;

int last[N],DFN[N],fa[N],d[N],d_[N],root[N],top[N],hea[N],size[N],head[N];
int adj[M_],stp[M_];
int tov[E],nxt[E];
int val[N<<2];
int n,m,tot,cnt,idx,T,ans,cas;

void insert(int x,int y){tov[++tot]=y,nxt[tot]=last[x],last[x]=tot;}

void hang(int x,int y){adj[++cnt]=y,stp[cnt]=head[x],head[x]=cnt;}

struct segment_tree
{
    int tag[S],mi[S];
    int son[S][2];
    queue<int> avl;

    int newnode(int x)
    {
        int np=avl.front();avl.pop();
        mi[np]=val[x],tag[np]=son[np][0]=son[np][1]=0;
        return np;
    }

    void release(int rt){avl.push(rt);}

    void update(int x,int l,int r,int rt)
    {
        mi[rt]=m+1;
        if (l==r) mi[rt]=val[x];
        else
        {
            if (son[rt][0]) mi[rt]=min(mi[rt],mi[son[rt][0]]);
            else mi[rt]=min(mi[rt],val[x<<1]);
            if (son[rt][1]) mi[rt]=min(mi[rt],mi[son[rt][1]]);
            else mi[rt]=min(mi[rt],val[x<<1|1]);
        }
        mi[rt]+=tag[rt];
    }

    void modify(int &rt,int x,int st,int en,int l,int r,int delta)
    {
        if (st>en) return;
        if (!rt) rt=newnode(x);
        if (st==l&&en==r)
        {
            tag[rt]+=delta,mi[rt]+=delta;
            return;
        }
        int mid=l+r>>1;
        if (en<=mid) modify(son[rt][0],x<<1,st,en,l,mid,delta);
        else if (mid+1<=st) modify(son[rt][1],x<<1|1,st,en,mid+1,r,delta);
        else modify(son[rt][0],x<<1,st,mid,l,mid,delta),modify(son[rt][1],x<<1|1,mid+1,en,mid+1,r,delta);
        update(x,l,r,rt);
    }

    int merge(int p,int l,int r,int x,int y)
    {
        if (!x||!y) return x^y;
        int mid=l+r>>1;
        tag[x]+=tag[y],son[x][0]=merge(p<<1,l,mid,son[x][0],son[y][0]),son[x][1]=merge(p<<1|1,mid+1,r,son[x][1],son[y][1]),update(p,l,r,x);
        return release(y),x;
    }
}t;

void change(int &rt,int x,int delta){for (int y;x;x=fa[y]) y=top[x],t.modify(rt,1,DFN[y]==1?2:DFN[y],DFN[x],1,idx,delta);}

void dfs(int x)
{
    size[x]=1,hea[x]=0;
    for (int i=last[x],y;i;i=nxt[i])
        if ((y=tov[i])!=fa[x])
        {
            fa[y]=x,dfs(y),size[x]+=size[y],d[x]+=d[y];
            if (!hea[x]||size[hea[x]]<size[y]) hea[x]=y;
        }
}

void HLD(int x,int tp)
{
    d_[DFN[x]=++idx]=d[x],top[x]=tp;
    if (hea[x]) HLD(hea[x],tp);
    for (int i=last[x],y;i;i=nxt[i])
        if ((y=tov[i])!=fa[x]&&y!=hea[x]) HLD(y,y);
}

void build(int x,int l,int r)
{
    if (l==r)
    {
        val[x]=d_[l];
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r),val[x]=min(val[x<<1],val[x<<1|1]);
}

void calc(int x)
{
    if (hea[x]) calc(hea[x]),root[x]=root[hea[x]];
    for (int i=last[x],y;i;i=nxt[i])
        if ((y=tov[i])!=fa[x]&&y!=hea[x]) calc(y),root[x]=t.merge(1,1,idx,root[x],root[y]);
    for (int i=head[x],y;i;i=stp[i]) y=adj[i],change(root[x],y,-2);
    if (x!=1)
    {
        t.modify(root[x],1,DFN[x],DFN[x],1,idx,M),ans=min(ans,d[x]+t.mi[root[x]]),t.modify(root[x],1,DFN[x],DFN[x],1,idx,-M);
        for (int i=last[x],y;i;i=nxt[i])
            if ((y=tov[i])!=fa[x]) ans=min(ans,d[x]-d[y]);
    }
}

void clear()
{
    tot=cnt=0,memset(last,0,sizeof last),memset(head,0,sizeof head),memset(nxt,0,sizeof nxt),memset(stp,0,sizeof stp);
    memset(d,0,sizeof d),memset(hea,0,sizeof hea),memset(root,0,sizeof root);
    for (;!t.avl.empty();t.avl.pop());
    for (int i=1;i<S;++i) t.avl.push(i);
}

int main()
{
    freopen("mincutcut.in","r",stdin),freopen("mincutcut.out","w",stdout);
    for (T=read();T--;)
    {
        clear(),n=read(),m=read();
        for (int i=1,x,y;i<n;++i) x=read(),y=read(),insert(x,y),insert(y,x);
        for (int i=1,x,y;i<=m-n+1;++i) ++d[x=read()],++d[y=read()],hang(x,y),hang(y,x);
        fa[1]=0,dfs(1),idx=0,HLD(1,1),build(1,1,n),t.mi[0]=ans=m+1,calc(1);
        printf("Case #%d: %d\n",++cas,ans+2);
    }
    fclose(stdin),fclose(stdout);
    return 0;
}