运输任务

Posted on Edited on In

题目大意：一棵树，要依此经过好多点， 有的有向边每经过一次，费用翻倍，问最后的费用是多少

看到这些路径问题，就联想树上差分

我们记录一个\(up[x]\)表示由x指出来的边，\(down[x]\)表示由\(fa[x]\)指向x的边

然后树上差分一下就好了

回顾树上差分的知识：

点差分：

\(d[s]-1,d[lca]-1\)相当于对他的lca直系的left侧仅次于lca的一个节点到s进行操作，公式表示为\(d[lca]-1=a[lca]-(a[left]+1)\)

\(d[t]-1,d[lca_{fa}]-1\)相当于对lca到lca的直系的right侧直到t进行操作，公式表示为\(d[lca_{fa}] - 1=a[lca_{fa}]-(a[lca]+1)\)

边差分：

\(d[s]-1,d[t]-1,d[lca]-=2\)

还有一个小知识：\(2^0+2^1+2^2+...2^i=2^{i+1}-1​\)

然后这就是一个树上差分的板子题了，注意开ll并且1e6的K

代码如下：

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
#include <bits/stdc++.h>
//#define int long long
#define ll long long

int n, m;
ll res;
int dep[N], fa[N][34], base[N], up[N], down[N];

inline void dfs(int x)
{
    int i, y;
    for (i = 1; i <= 30; ++ i)
    {
        if (fa[x][i - 1]) fa[x][i] = fa[fa[x][i - 1]][i - 1];
        else break;
    }
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (y == fa[x][0]) continue;
        fa[y][0] = x;
        dep[y] = dep[x] + 1;
        dfs(y);
    }
}

inline int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    int delta = dep[x] - dep[y], i;
    for (i = 30; i >= 0; -- i)
    {
        if (delta & (1 << i))
        {
            x = fa[x][i];
        }
    }
    if (x == y) return x;
    for (i = 30; i >= 0; -- i)
    {
        if (fa[x][i] != fa[y][i])
        {
            x = fa[x][i], y = fa[y][i];
        }
    }
    return fa[x][0];
}

inline void Gres(int x, int yhm_fa)
{
    int i, y;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (y == yhm_fa) continue;
        Gres(y, x);
        up[x] += up[y];
        down[x] += down[y];
        if (len[i] == 1) res = (res + (1ll * base[down[y]] - 1 + mod) % mod) % mod;
        else if (len[i ^ 1] == 1) res = ((res + 1ll * base[up[y]] - 1 + mod) % mod) % mod;
    }
    return;
}

signed main()
{
    int i, x, y, z; n = read();
    
    for (i = 1; i < n; ++ i)
    {
        x = read(), y = read(), z = read();
        if (! z) add_edge(x, y, z), add_edge(y, x, z);
        else add_edge(x, y, 0), add_edge(y, x, 1);
    }
    m = read();
    dfs(1), base[0] = 1;
    for (i = 1; i <= m; ++ i) base[i] = (1ll * base[i - 1] * 2) % mod;

    x = 1;
    for (i = 1; i <= m; ++ i)
    {
        y = read();
        int LCA = lca(x, y);
        ++ up[x], -- up[LCA];
        ++ down[y], -- down[LCA];
        x = y;
    }

    Gres(1, 0);

    put(res);
    return 0;
}

总结：

期望得分：100+0+50pts

实际得分：50+0+20pts

第一题因为ll和一个小细节挂掉50分，第二题没想到树上差分，第三题暴力写的太暴力了，T了30分

归根结底是没有对知识构建一个合理的知识体系，以后要多自己回想知识体系

毕竟每一章节算法不多，枚举用哪个就好。。