Znzryb's Blog
0%

ABC- 378 - F - Add One Edge 2

Posted on Edited on

AC代码

image

我判断这道题是一道树状dp问题

以上是树状dp问题的基本思路（说白了就是递归，dfs嘛，简单）

当然我这个做法和树上dp可能还是有点不同，但都是靠子树返回的值进行计算

注释应该足够清楚，主要思路就是通过下面的节点传递上来的可传播validS进行求解，然后用dfs2打了一下链状数据结构的补丁

AC

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N = static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,ans,recAns;    // recAns,即rectify ans
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要求解包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
    }
    if(g[x].size()==2) {
        ans+=res;
        return 1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

void dfs2(ll x) {   // 把链状数据剪掉，即打补丁的dfs
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        if(g[fx].size()==2 && g[x].size()==2)
            recAns+=1;
        dfs2(fx);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vis[1]=true;
    dfs(1);
    vis.reset();
    vis[1]=true;
    dfs2(1);
    ans-=recAns;
    cout<<ans<<endl;
}
// AC https://atcoder.jp/contests/abc378/submissions/59465360

心路历程（WA，TLE，MLE……）

没过样例，主要问题在这里

degree==2的点也会阻隔validS传播

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,dp[N],ans;
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
        // if(g[fx].size()>3 || g[fx].size()<=1)
        //     res+=dfs(g[fx][i]/*,0*/);       // 不符合validS传播条件的点，阻断传播
        // else if(g[fx].size()==3)
        //     res+=dfs(g[fx][i]/*,validS*/);      // g[fx].size()==3，degree为3，可正常传播
        // else if(g[fx].size()==2)
        //     res+=dfs(g[fx][i]/*,validS+1*/);
    }
    if(g[x].size()==2) {
        ans+=res;
        return res+1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // for(int i=1;i<=n;i++) {
    //     dp[i]=-1;
    // }
    for(int i=1;i<=n;i++) {     // 防止图不联通
        // // 我凭感觉应该是只能从degree为1的点进入，即只连了一条边点
        // if(g[i].size()>1)
        //     continue;
        if(vis[i])
            continue;
        vis[i]=true;
        dfs(i);
    }
    cout<<ans<<endl;
}

这个代码样例过了，但是全错

主要问题在于输入链状数据，答案一定为0。但我这个程序有点小问题

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N = static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,dp[N],ans;
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
        // if(g[fx].size()>3 || g[fx].size()<=1)
        //     res+=dfs(g[fx][i]/*,0*/);       // 不符合validS传播条件的点，阻断传播
        // else if(g[fx].size()==3)
        //     res+=dfs(g[fx][i]/*,validS*/);      // g[fx].size()==3，degree为3，可正常传播
        // else if(g[fx].size()==2)
        //     res+=dfs(g[fx][i]/*,validS+1*/);
    }
    if(g[x].size()==2) {
        ans+=res;
        return 1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // for(int i=1;i<=n;i++) {
    //     dp[i]=-1;
    // }
    for(int i=1;i<=n;i++) {     // 防止图不联通
        // // 我凭感觉应该是只能从degree为1的点进入，即只连了一条边点
        // if(g[i].size()>1)
        //     continue;
        if(vis[i])
            continue;
        vis[i]=true;
        dfs(i);
    }
    cout<<ans<<endl;
}