BJ United R4 彼岸蔷薇

题意

给定一棵树与 条树上路径，求有多少对 使得加入路径 后 条路径的能够选出来的最大的点不相交的路径集合比原来大。

思路

太厉害了，赞美 EI！

考虑先求出每个点 能不能删，假设求出来了，你就会发现所有可删点的连通块中的所有路径都是可删的。

太厉害了，为什么呢？

首先 显然不能经过不合法点，然后证明如果边 上两个点都能删，那么两个点都删是没有影响的（然后归纳缩点即可）。

考虑反证，如果 不能都删的话，那么选 的时候， 必然被选，同时删 的时候， 必然被选。然后你发现 必然一个是一条路径的 LCA，另一个是路径的端点，于是这两条路径可以一块选并且答案变大了，于是 都不能删了。实在是太厉害了！

然后考虑怎么求呢？首先我们需要先求出原先 条路径的最大集合，这个可以直接 LCA 深度由大到小贪心放就可以了，证明比较显然。

然后如果根没有被选，那么根就可以被删（雾），这样就可以做到 了。然后你进一步考虑如果某个结点本来被选了，但是那条路径可以被替换并且不经过这个结点，那么这个结点也是可删的。

直接求一个选择路径能被哪些路径替换比较困难，不妨考虑未选路径能替换哪条路径。

首先这条未选路径 只能包含一个选择路径的 LCA，原因你画一下发现显然。

然后如果它没有交其他路径的话那就肯定能换，但是它可能在自己的 LCA 处还有别的选择路径。不过这没关系，我们知道如果它的 LCA 是一个可删点的话，那么上面这条路径就能被替换并且避开它，于是就变成前面的情况了，否则它就不能用于替换。

那么我们按照 DFS 的顺序来处理就好了，当我们在处理 这个已选择路径的 LCA 时，我们会有 路径从 往下走，此时实际上的下行路径可能会多于 ，不过每个点是被最多 条路径的覆盖的。此时我们知道，如果一个点没有被 条路径都覆盖，那么它就是可删的。所以我们在端点处打一个贡献，然后 DFS 回溯回来计数覆盖路径数即可。

由于我们按照选择路径的 LCA 把整棵树拆开之后，我们的回溯不会跨过这些 LCA，所以复杂度就是线性的，当然求 LCA 做到线性需要一些科技，我懒得写。

CODE

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
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=1000010,FSIZE=1<<26;
int n,m,dp[N],mx[N],s[N][21],all[N],num[N],l[N],r[N],up[N],to[N];
bool is[N],tag[N],can[N];
ll ans;
vector<pair<int,int>> p[N];
vector<int> t[N],rm[N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
int lca(int x,int y){
    if(dp[x]<dp[y]) swap(x,y);
    int l=x,r=y;
    for(int i=mx[l];dp[l]>dp[r];--i)
        if(dp[s[l][i]]>=dp[r]) l=s[l][i];
    if(l==r) return(l);
    for(int i=mx[l];~i;--i)
        if(s[l][i]!=s[r][i]){
            l=s[l][i];
            r=s[r][i];
        }
    return(s[l][0]);
}
void dfs1(int x,int fa=0){
    dp[x]=dp[s[x][0]=fa]+1;
    for(int &i=mx[x];(s[x][i+1]=s[s[x][i]][i]);++i);
    for(int i:t[x]) if(i!=fa) dfs1(i,x);
}
void down(int x,int fa){
    tag[x]=1;
    for(int i:t[x])
        if(i!=fa&&!tag[i]) down(i,x);
}
void dfs2(int x,int fa=0){
    for(int i:t[x])
        if(i!=fa) dfs2(i,x);
    for(auto i:p[x])
        if(!tag[i.first]&&!tag[i.second]){
            is[num[x]=x]=1;
            return(down(x,fa));
        }
}
void dfs3(int x,int fa=0){
    all[x]=all[fa]+is[x];
    num[x]^=num[fa];
    for(int i:t[x]) if(i!=fa) dfs3(i,x);
}
void push(int cnt,int x,int fa){
    if(is[x]) return;
    for(int i:t[x])
        if(i!=fa){
            push(cnt,i,x);
            to[x]+=to[i];
        }
    if(to[x]<cnt) can[x]=1;
}
void dfs4(int x,int fa=0){
    if(is[x]){
        int cnt=0;
        for(int i:rm[x])
            if(up[i]==x||can[up[i]]){
                ++to[l[i]];
                ++to[r[i]];
                ++cnt;
            }
        is[x]=0;
        push(cnt,x,fa);
        for(int i:rm[x])
            if(up[i]==x||can[up[i]])
                to[l[i]]=to[r[i]]=0;
    }
    for(int i:t[x]) if(i!=fa) dfs4(i,x);
}
int count(int x,int fa=0){
    can[x]=0;
    int re=1;
    for(int i:t[x]) if(i!=fa&&can[i]) re+=count(i,x);
    return(re);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);read(m);
    for(int i=1,x,y;i<n;++i){
        read(x);read(y);
        t[x].push_back(y);
        t[y].push_back(x);
    }
    dfs1(1);
    for(int i=1;i<=m;++i){
        read(l[i]);read(r[i]);
        p[up[i]=lca(l[i],r[i])].emplace_back(l[i],r[i]);
    }
    dfs2(1);
    dfs3(1);
    for(int i=1;i<=m;++i)
        if(all[l[i]]+all[r[i]]-all[up[i]]-all[s[up[i]][0]]==1)
            rm[num[l[i]]^num[r[i]]^num[up[i]]^num[s[up[i]][0]]].push_back(i);
    if(!is[1]) push(1,1,0);
    dfs4(1);
    for(int i=1;i<=n;++i)
        if(can[i]){
            int x=count(i);
            ans+=(ll)x*x;
        }
    printf("%lld\n",ans);
    return(0);
}
≡