之所以写练习就是因为写总结太麻烦了(捂脸
其实说不定会写的qwq以后再说吧

参考

1分治算法在树的路径问题中的应用

树的分治、树上动规

树因其特有的拓扑性使得其有许多良好的性质可以使用。
树dp的无后效性是树dp的一个基础。
对于一类树上路径问题,dp的转移状态可能数量巨大。所以考虑分治。
对有根树上的路径,其有两种可能:1°过根;2°不过根(在某一子树里)。
容易发现对2°只需分治递归处理即可。

点分治

重心保证了对所有点最大子树的size最小。
可以证明
1°重心一定存在且至多为2;(点分可行性)
2°重心 $ G $ 最大的一个子树的size $ \max_{i \in succ(G)} |V_i| < \frac{n}{2} $。(时间复杂度)
选取重心,递归处理每棵子树。每次递归规模至少减半,由 Master Theorem 时间复杂度为 $ O(n \lg n) $ 。

边分治

选取一条中心边,去掉形成两棵子树大小相差最小。
[1]中给出一个定理:如果一棵树中每个点的度均不大于$ D $,那么存在一条边
使得分出的两棵子树的结点个数在 $ [\frac{N}{D+1},\frac{ND}{D+1}], N \ge 2 $。
证明基于这样一个基本事实:两棵子树较大一棵的最大子树的大小满足 $ P \ge \frac{S-1}{D-1} $;证明过程此处略。
由于 $ D $ 最坏是 $ O(N) $ 级别的(考虑“菊花树”,所有非1号点均直接与1号点连边形成的树),复杂度较高。

POJ 1741

求树上路径和不大于给定 $ K $ 的点对个数,不考虑点对顺序。

DFS枚举是平方级别,而树DP转移依赖于$ K=10^9 $级别。
考虑点分。
对当前树重心 $ G $,只需讨论以 $ G $ 为根时路径过其的情况。
处理出所有节点到根的距离 $ d $,现在就是求 $ d(i)+d(j) \le K $ 且 $ i, j $ 分属不同子树的对数。容易发现其为$ d(i)+d(j) \le K $ 的点对对数减去所有子树中满足 $ d(i)+d(j) \le K $ 的点对对数。注意此时并未分治,$ d $ 数组仍然是以 $ G $ 为根的情况。
将 $ d $ 数组排序后便可以计算得到答案了。注意到其满足单调性(具体一点说就是,设$ j $ 是满足 $ d_i+d_j $ 的最大$ j $,则对$ i + 1 $满足最大的 $ j' $必有$ d_{j'}
le d_j $,因为排完序了,所以比它小的数的个数可以轻易得出),两个指针分别从前后扫就可以了。


来说说实现第一次实现过程中犯的傻事。(TLE x inf)

  1. 分治过程中未更新子树size(需重新求重心,而其依赖于当前树的大小)
  2. 求重心过程中没有更新size最大值导致没有更新重心
  3. 两个dfs并在一起写还没有把重心拎出来独立存
  4. 统计d数组忘了加重心本身
  5. 把d数组更新放在dfs入口之后
  6. 计算两指针没有判距离为负数
  7. 后续统计递归拿入口节点当根而非重心
  8. 我这种沙茶为什么要活着

码(172ms 1108kB)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e4 + 10, INF = 0x3f3f3f3f;
int n, k;
struct N{int v, w, n;} e[maxn << 1];
int h[maxn], ecnt = 1;
inline void add_edge(int u, int v, int w) {e[ecnt] = (N){v, w, h[u]}; h[u] = ecnt++;}
int G, s, a[maxn], ac, size[maxn], depth[maxn];
bool unexist[maxn];
void getG(int u, int f)
{
    int _max = 0; size[u] = 1;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f && !unexist[v])
         getG(v, u), size[u] += size[v], _max = max(_max, size[v]);
    _max = max(_max, n - size[u]);
    if(_max < s) G = u, s = _max;
}
void getDeep(int u, int f)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f && !unexist[v])
         a[ac++] = depth[v] = depth[u] + e[i].w, getDeep(v, u);
}
int calc()
{
    int ans = 0;
    sort(a, a + ac);
    for(int i = 0, j = ac - 1; i < j; i++)
    {
        while(a[i] + a[j] > k && j > i) j--;
        ans += j - i;
    }
    return ans;
}
int dc(int u = 1)
{
    s = INF; getG(u, 0);
    a[0] = 0, ac = 1, depth[G] = 0; unexist[G] = true;
    getDeep(G, 0);
    int ans = calc();
    for(int i = h[G], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!unexist[v])
    {
        a[0] = depth[v] = e[i].w, ac = 1;
        getDeep(v, 0);
        ans -= calc();
    }
    for(int i = h[G], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!unexist[v])
        n = size[v], ans += dc(v);
    return ans;
}
int main()
{
    while(read(n, k), n || k)
    {
        memset(h, 0, sizeof h); ecnt = 1; memset(unexist, false, sizeof unexist);
        for(int i = 1, u, v, l; i < n; i++) read(u, v, l), add_edge(u, v, l), add_edge(v, u, l);
        printf("%d\n", dc());
    }
    return 0;
}

SPOJ FTOUR2

一棵树上有若干个黑点,边有权值。问树上路径在经过不超k个黑点的情况下边权和最大值。

有了上一题的基础我们继续考虑点分。
令$ f[i,j] $ 表示根第 $ i $ 棵子树,经过 $ j $ 个黑点能到达的最远距离。
则有答案为 $ \max{f[i_1,j_1]+f[i_2,j_2] | i_1 \neq i_2, j_1 + j_2 \le k} $。
考虑前缀和即我们吞掉 $ i $ 这一维,即令$ f[j] $表示以处理的子树中经过不超过j个黑点的最远距离,对当前子树每个$ f[j'] $查询之前 $ [1,k-j'] $ 的最大值,其和即为所求可能答案,用数据结构维护可以做到 $ O(n \lg n) $,总时间为$ O(n \lg^2 n) $。
考虑不使用数据结构。将$ f $数组的定义修改为不大于$ j $个黑点的距离最大值,即再求一次前缀和。我们记录每棵子树最多可能经过 $ c_i $ 个黑点。则每次暴力更新 $ f $数组的复杂度为 $ \sum_i \max_{1 \le j \le i} c_j = \Omega(n^2) $,最坏总时间为 $ \Omega(n^2 \lg n) $。
我们以 $ c_i $ 为关键字排序,则易有复杂度下降为$ O(n) $。,算上排序总共$ O(n \lg n) $,总时间为$ O(n \lg n) $


MDZZ我真的感觉以我的智商不适合竞赛。
这道SB题调了我一天+.
分错误类型自我检讨:(泣

  1. TLE
    1.1 没有用上面推出来的性质用cc[a[ii]]而是每次更新到cc[a[ac - 1]](woc那我费那么大劲推性质干嘛

1.2 cc[]计算错了,算了子树黑点总数(woc我最擅长证完一个优美的性质然后不用我$^{tm}$真是天才

  1. WA
    2.1 又忘了更新子树size

2.2 为使f[k-b-c[u]-c[G]]得到正确的值需要对cc[a[ii-1]]min而非cc[a[ii]]或者cc[a[ac - 1]]
2.3 要注意c[G]即结点标记不能下传,或则会导致子树重复计算根节点的标记

  1. 吐槽我的变量名吧(捂脸 md开始向 @whj 的魔幻现实主义看齐了

有一个hack点好像网上代码也不一定过得去

[IN]

4 1 2
1 4
1 2 1
1 3 2
1 4 4
[OUT]
3

码(490ms 36864kB)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 2e5 + 100, INF = 0x7fffffff;
bool c[maxn], vis[maxn];
struct E{int v, w, n;} e[maxn << 1];
int h[maxn], ecnt = 1, n, k;
inline void add_edge(int u, int v, int w){e[ecnt] = (E){v, w, h[u]}; h[u] = ecnt++;}
int G, s, size[maxn], cc[maxn];
void getG(int u, int f)
{
    size[u] = 1, cc[u] = c[u]; int _max = 0, ret = 0;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f && !vis[v])
        getG(v, u), size[u] += size[v], _max = max(size[v], _max), ret = max(cc[v], ret);
    _max = max(_max, n - size[u]);
    if(_max < s) s = _max, G = u;
    cc[u] += ret;
}
int ans = 0, d[maxn], f[maxn], ss;
int a[maxn], ac, di[maxn], ii;
void dfs(int u, int fa, int b, int hi)
{
    if(b > k) return;
    d[b + c[u]] = max(hi, d[b + c[u]]);
    if(k >= b + c[u] + c[G]) ans = max(ans, f[min(k - b - c[u] - c[G], cc[a[ii - 1]])] + (d[b + c[u]]));
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != fa && !vis[v])
        dfs(v, u, b + c[u], hi + e[i].w);
}
inline bool cmp(int a, int b){return cc[a] < cc[b];}
void dc(int u = 1)
{
    s = INF; getG(u, 0); vis[G] = true; getG(G, 0);
    ac = 0;
    for(int i = h[G], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!vis[v])
        a[ac++] = v, di[v] = e[i].w;
    sort(a, a + ac, cmp);
    for(int j = 0; j <= cc[a[ac - 1]]; j++) f[j] = 0;
    for(ii = 0; ii < ac; ii++)
    {
        for(int j = 0; j <= cc[a[ii]]; j++) d[j] = 0;
        dfs(a[ii], G, 0, di[a[ii]]);
        f[0] = max(f[0], d[0]);
        for(int j = 1; j <= cc[a[ii]]; j++)
            f[j] = max(max(f[j], f[j - 1]), d[j]);
    }
    for(int i = h[G], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!vis[v])
        n = size[v], dc(v);
}
int main()
{
    int m; read(n, k, m);
    int a; while(m--) read(a), c[a] = true;
    for(int i = 1, u, v, w; i < n; i++) read(u, v, w), add_edge(u, v, w), add_edge(v, u, w);
    dc();
    printf("%d\n", ans);
    return 0;
}

SPOJ QTREE4

给一棵初始全为白点的树,两种操作:某点反色;最远两白点距离。

@whj 教了我点分写法orz
对每个重心维护以下两个集合:当前树所有点到上一级重心的距离,记为 $ q_1 $ ;所有子树的 $ q_2 $ 中的最大值的集合,记为 $ q_1 $.此外维护一个全局数组 $ gq $,记录每个 $ q_1 $ 前两个最大值的和。易知 $ gq $ 最大值即为答案。
注意到每个集合的状态只依赖于另一个集合的最大值,所以用堆维护即可。
对初始状态 $ q_2, q_1, gq $ 均容易求出。考虑修改的过程。每次修改的时候都会影响其上所有重心层的 $ q_2 $,继而影响 $ q_1 $,继而影响 $ gq $。影响的过程即是重新计算,把原来的数先删掉再计算新的数加进去。
具体删除的方法,可以再维护一个堆把待删除的数全部加进去。把一些数“标记”为删除。


TLE 于是调了半天。
优化了半天换个语言交就 A 了。
抱拳[抱拳]
return GG;


自婊:

  1. $ q_2 $ 忘记加到上一个重心的边,统计的时候没用重心存
  2. $ q_1 $ 如果自己是白色要加自己
  3. 在 sboj 上要多尝试其他语言!!!

码(1120ms 74752kB)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
char buf[8000000],*pt = buf,*o = buf;
inline int getint(){
    int f = 1,x = 0;
    while((*pt != '-') && (*pt < '0' || *pt > '9'))    pt ++;
    if(*pt == '-')    f = -1,pt ++;    else    x = *pt++ - 48;
    while(*pt >= '0' && *pt <= '9')    x = x * 10 + *pt ++ - 48;
    return x * f;
}
inline char getch(){
    char ch;
    while(*pt < 'A' || *pt > 'Z')    pt ++;
    ch=*pt;pt++;    
    return ch;
}
const int maxn = 1e5 + 100, INF = 0x3f3f3f3f;
int n; 
struct E{int v, w, n; } e[maxn << 1];
int h[maxn], ecnt = 1;
inline void add_edge(int u, int v, int w) {e[ecnt] = (E){v, w, h[u]}; h[u] = ecnt++;}
int fa[maxn][20], depth[maxn], d[maxn];
void getfa(int u, int f = 0)
{
    fa[u][0] = f;
    for(int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
        depth[v] = depth[u] + 1, d[v] = d[u] + e[i].w, getfa(v, u);
}
int getlca(int u, int v)
{
    if(depth[u] < depth[v]) swap(u, v);
    int delta = depth[u] - depth[v];
    for(int i = 0; i < 20; i++) if((1 << i) & delta)
        u = fa[u][i];
    if(u == v) return u;
    for(int i = 19; ~i; i--) if(fa[u][i] != fa[v][i])
        u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
int size[maxn], G, s, fa2[maxn], tmp;
bool vis[maxn], c[maxn];
void getG(int u, int f = 0)
{
    int _max = 0; size[u] = 1;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f && !vis[v])
        getG(v, u), size[u] += size[v], _max = max(_max, size[v]);
    _max = max(_max, n - size[u]);
    if(_max < s) s = _max, G = u;
}
priority_queue<int> q1[maxn], dq1[maxn], q2[maxn], dq2[maxn], gq, dgq;
void getq2(int u, int t, int f = 0, int len = 0)
{
    q2[t].push(len);
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f && !vis[v])
        getq2(v, t, u, len + e[i].w);
}
inline void cleargq() {while(!dgq.empty() && !gq.empty() && gq.top() == dgq.top()) gq.pop(), dgq.pop();}
inline void clearq1(int u) {while(!dq1[u].empty() && !q1[u].empty() && q1[u].top() == dq1[u].top()) q1[u].pop(), dq1[u].pop();}
inline void clearq2(int u) {while(!dq2[u].empty() && !q2[u].empty() && q2[u].top() == dq2[u].top()) q2[u].pop(), dq2[u].pop();}
inline int getsum(int u)
{
    clearq1(u);
    if(q1[u].empty()) return -INF; 
    int t = q1[u].top(); q1[u].pop(); clearq1(u);
    if(q1[u].empty()) {q1[u].push(t); return t == 0 ? 0 : -INF;}
    t += q1[u].top(); q1[u].push(t - q1[u].top());
    return t;
}
int dfs(int u = 1, int f = 0, int w = 0)
{
    s = INF; getG(u); fa2[G] = f;
    getq2(u, G, f, w); int GG = G;
    vis[G] = true;
    for(int i = h[G], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!vis[v] && v != f)
    {
        n = size[v]; int g = dfs(v, GG, e[i].w);
        if(!q2[v].empty()) q1[GG].push(q2[g].top());
    }
    q1[GG].push(0);
    tmp = getsum(GG); if(tmp != -INF) gq.push(tmp);
    return GG;
}
inline int query() {cleargq(); return gq.empty() ? -1 : max(0, gq.top());}
void modify(int u, int a)
{
    if(c[a])
    {
        tmp = getsum(u); if(tmp != -INF) dgq.push(tmp); 
        q1[u].push(0);
        tmp = getsum(u); if(tmp != -INF) gq.push(tmp);
    }
    else
    {
        tmp = getsum(u); if(tmp != -INF) dgq.push(tmp); 
        dq1[u].push(0); 
        tmp = getsum(u); if(tmp != -INF) gq.push(tmp);
    }
    c[a] ^= 1;
    for(; fa2[u]; u = fa2[u])
    {
        clearq1(fa2[u]); if((tmp = getsum(fa2[u])) != -INF) dgq.push(tmp);
        clearq2(u); if(!q2[u].empty()) dq1[fa2[u]].push(q2[u].top());
        tmp = d[fa2[u]] + d[a] - 2 * d[getlca(fa2[u], a)];
        if(!c[a]) q2[u].push(tmp); else dq2[u].push(tmp);
        clearq2(u); if(!q2[u].empty()) q1[fa2[u]].push(q2[u].top()); 
        clearq1(fa2[u]); if((tmp = getsum(fa2[u])) != -INF) gq.push(tmp);
    }
}
int u, v, w, m;
char ch;
int main()
{
    fread(buf,1,8000000,stdin);
    n = getint();
    for(int i = 1; i < n; i++) u = getint(), v = getint(), w = getint(), add_edge(u, v, w), add_edge(v, u, w);
    getfa(1);
    dfs();
    m = getint(), u;
    while(m--)
    {
        ch = getch();
        if(ch == 'A') (u = query()) == -1 ? puts("They have disappeared.") : printf("%d\n", u);
        else u = getint(), modify(u, u);
    }
    return 0;
}

边分的优化

注意到边分的复杂度跟最大度有关,这启发我们对每个点度数进行恒等变化。
我们考虑“虚点”,其为树上一个点,但是边权、点权均不存在。即是在统计中不纳入统计。
在原树中添加虚点,使其变为二叉树,加点不超过 $ O(n) $ 个,便可以使分治复杂度保证为 $ O(\lg n) $ 了。
具体怎么加点,我有一个想法是把一个点的所有儿子存到队列,然后每次取出两个并起来再加到队列,直到只剩下两个为止。网上的做法好像是每层递归加一个点,但感觉那样子树长得好丑(……)
反正我不打边分。

链分治

以下默认各位应该清楚树链剖分是什么。
我们回想轻重树剖的思路,是每次找到重儿子形成的链(重链,or in general, preferred path),各个重链间由轻边连接而成,此时整棵树被分成 $ O(\lg n) $ 条链。在链即线性结构上进行统计是平凡的,也就是说轻重树剖帮助我们更快的进行树上路径的统计。
事实上涉及树上路径的统计,使用链都是一个很好的分治思路。
所以类似点分边分,我们考虑链分。每次取出一条链,操作/统计,递归分治。
链上信息高效维护需要使用高级数据结构。

链分对 SPOJ QTREE4 的解

BZOJ 4012

标签: 树分治

添加新评论