专题 LCA

1.[JLOI2014]松鼠的新家

 

 solution：路径覆盖板题，对于ai，只需要将cnt[ai]和cnt[ai+1]各加1，并将它们的lca和lca的父亲的cnt各减1，最后用一遍dfs，统计一下即可。

2.[NOIP2016 DAY1]天天爱跑步

 

duliu题

不多讲了，这里贴个代码，反正也无法理解。。。

#include 

using namespace std;

const int N = 300000;
const int maxn = 600005;

struct node {
    int to, nxt;
}e[maxn][3];

int head[maxn][3], tot[3], dep[maxn], dis[maxn], w[maxn], fa[maxn][21], s[maxn], t[maxn], num[maxn][2], cnt[maxn], ans[maxn];

inline void add_e(int u, int v, int id) 
{
    e[++tot[id]][id].to = v;
    e[tot[id]][id].nxt = head[u][id];
    head[u][id] = tot[id];
}

void dfs(int u)
{
    for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u][0]; i; i = e[i][0].nxt)
    {
        int v = e[i][0].to;
        if (v == fa[u][0]) continue;
        fa[v][0] = u, dep[v] = dep[u] + 1;
        dfs(v);
    }
}

int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    int k = dep[x] - dep[y];
    for (int i = 0; i <= 20; i++)
    {
        if (k & (1 << i)) x = fa[x][i];
    }
    if (x == y) return x;
    for (int i = 20; ~i; i--)
    {
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

void dfs2(int u)
{
    int dt1 = num[w[u] + dep[u]][0], dt2 = num[w[u] - dep[u] + N][1];
    for (int i = head[u][0]; i; i = e[i][0].nxt)
    {
        int v = e[i][0].to;
        if (v == fa[u][0]) continue;
        dfs2(v);
    }
    num[dep[u]][0] += cnt[u];
    for (int i = head[u][1]; i; i = e[i][1].nxt)
    {
        int v = e[i][1].to;
        ++num[dis[v] - dep[t[v]] + N][1];
    }
    ans[u] += (num[w[u] + dep[u]][0] + num[w[u] - dep[u] + N][1] - dt1 - dt2);
    for (int i = head[u][2]; i; i = e[i][2].nxt)
    {
        int v = e[i][2].to;
        --num[dep[s[v]]][0];
        --num[dis[v] - dep[t[v]] + N][1];
    }
}

char buf[1 << 22], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

template <class T>
inline void rd(T &a)
{
    char ch = getchar(); T x = 0, f = 1;
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    a = x;
}

int main()
{
    int n, m;
    rd(n), rd(m);
    for (int i = 1, x, y; i < n; i++) 
    {
        rd(x), rd(y);
        add_e(x, y, 0);
        add_e(y, x, 0);
    }
    dfs(1);
    for (int i = 1; i <= n; i++) rd(w[i]);
    for (int i = 1; i <= m; i++)
    {
        rd(s[i]), rd(t[i]);
        int l = lca(s[i], t[i]);
        dis[i] = dep[s[i]] + dep[t[i]] - 2 * dep[l];
        ++cnt[s[i]];
        add_e(t[i], i, 1);
        add_e(l, i, 2);
        if (dep[l] + w[l] == dep[s[i]]) --ans[l];
    }
    dfs2(1);
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}

3.[NOIP2012 day2]疫情控制

 

 solution：大概思路就是先让所有军队往首都走，如果走不到首都就尽可能往上走，来控制尽可能多的城市，这个贪心思路显然。第二步，我们标记首都的哪些儿子已被控制，如果一个儿子只有一支军队驻扎，那么就让它停在原处，否则就将剩余时间最少的军队停在原处，剩下的我们就可以调兵遣将，将未被控制的儿子所需的时间从小到大排序，将军队的剩余时间也从小到大排序，然后尽量匹配（因为如果一支军队无法驻扎当前所需时间最小的儿子，它显然不能驻扎到任何儿子去，即显然无用），最后判断是否合法即可。

4.冷战

 

 solution：这个题强制在线，我们可以考虑并查集按秩合并和lca（乱搞一下，只需要记录一下在第几条边联通就行了）。

5.叶子的染色

 

 solution：其实是一个树形dp（我也不知道它为什么来到了这里qwq），但是我们还是来看一看这道题。

首先设一个状态，就是f[i][j]为以i为根的子树中满足题意，且i号节点涂第j种颜色的最小代价。可以发现，当i和它的儿子同色时，可以不用将它的儿子涂色，否则需要。那么我们假设每个点强制涂色，最后再将代价减掉即可。

高一下复习

相关

标签