前缀和与差分都能给人意想不到的惊喜

懵逼的 题目

传送至 Luogu (火狐蜜汁上不去…差评)

扯淡的 题解

做差分的时候做的这道题…没错我都知道这是差分了还是WA了…
emmmmm….显然这是区间修改单点查询…于是想到差分…于是就是一道裸的树上差分…啊裆燃还得求个LCA…
然而我一开始想到的是: 记录每一个点和他父亲的差值PC[](又是奇奇怪怪的变量名)…找到两点的LCA, PC[LCA++], PC[s]--, PC[t]--;, 然后从上往下推, 后来发现过不了样例…然后知道如果LCA就是s或者t的话会GG, 所以让LCA的一段保持不变就好了…然后WAWAWAWA…GG
后来发现题解里都是记录sum[]代表一个节点和所有子树的和的差值…然后回溯的时候更新ans…诶为什么这样是对的啊QAQ?
后来发现有这么一种情况

这里写图片描述

如果s = 3, t = 5, 5是LCA, 又是终点, 按理说只应该PC[t]++才对…但是如果只是PC[t]++, 节点6的点权就会受到影响…
所以正确的程序应该是让”其他的子节点”的PC值--, 但是倍增求的LCA似乎并没有办法记录st在LCA的哪一颗子树上…于是GG

改成记录sum[]就A了…

对了今天突然想起来修改的问题…修改的代码大概是这个样的…

scanf("%d%d", &x, &y);
int lcaxy = lca(x, y);

sum[x]++;
sum[y]++;

sum[lcaxy]--;

sum[father[lcaxy]]--;

sum[x]++; sum[y]++; 就是所有以x, y为子树的节点值都要++
sum[lcaxy]--; 因为节点lcaxyx, y两者为子树, 所以其实lcaxy的值是+=2的…所以要--, 来保证节点lcaxy的值也是+=1
sum[father[lcaxy]]--; 因为lcaxy上面(假定有根)的节点都不用变了…所以--好咯…

沙茶的 代码

WA

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (50000 + 5)
#define MAXL (20 + 5)
#define MAXQ (100000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int t = a;a = b;b = t;}

const int root = 1;
struct edg
{
    int from;
    int to;
    int next;
}b[MAXN << 1];
int g[MAXN];
int cntb;

int fa[MAXN];
int d[MAXN][MAXL];
int deep[MAXN];
int lgn;

int pc[MAXN];

int n;
int q;

int ans;

void adn(int, int);
int lca(int, int);
void init(int, int);
void dfs(int, int);
int lg(int);
void solve();
void chan(int);
int main()
{
    scanf("%d%d", &n, &q);
    lgn = lg(n);
    int srx, sry;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    d[root][0] = fa[root] = root;
    init(root, 1);
    solve();
    dfs(root, 0);
    printf("%d", ans);
    return 0;
}
int lg(int x)
{
    for (int i = 1; ; i++)
    {
        if ((1 << i) > x)
            return i;
    }
}
void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}
void init(int dq, int de)
{
    deep[dq] = de;
    for (int i = 1; i <= lgn; i++)
    {
        d[dq][i] = d[d[dq][i - 1]][i - 1];
    }
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (fa[dq] != b[i].to)
        {
            d[b[i].to][0] = fa[b[i].to] = dq;
            init(b[i].to, de + 1);
        }
    }
}
int lca(int x, int y)
{
    if (deep[x] > deep[y])
    {
        swap(x, y);
    }
    for (int i = lgn; i >= 0; i--)
    {
        if (deep[d[y][i]] >= deep[x])
        {
            y = d[y][i];
        }
    }
    if (x == y)
        return x;
    for (int i = lgn; i >= 0; i--)
    {
        if (d[y][i] != d[x][i])
        {
            y = d[y][i], x = d[x][i];
        }
    }
    return fa[x];
}
void solve()
{
    int srx, sry;
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &srx, &sry);
        int lcxy = lca(srx, sry);
        ++pc[lcxy];
        if (lcxy != srx)
            chan(srx);
        if (lcxy != sry)
            chan(sry);
    }
}
void chan(int x)
{
    for (int i = g[x]; i; i = b[i].next)
    {
        if (b[i].to != fa[x])
            --pc[b[i].to];
    }
}
void dfs(int dq, int zh)
{
    ans = max(ans, pc[dq] + zh);
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].to != fa[dq])
            dfs(b[i].to, zh + pc[dq]);
    }
}

/*
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
*/

AC

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (50000 + 5)
#define MAXL (20 + 5)
#define MAXQ (100000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int t = a;a = b;b = t;}

const int root = 1;
struct edg
{
    int from;
    int to;
    int next;
}b[MAXN << 1];
int g[MAXN];
int cntb;

int fa[MAXN];
int d[MAXN][MAXL];
int deep[MAXN];
int lgn;

int pc[MAXN];

int n;
int q;

int ans;

void adn(int, int);
int lca(int, int);
void init(int, int);
void dfs(int);
int lg(int);
void solve();
void chan(int);
int main()
{
    scanf("%d%d", &n, &q);
    lgn = lg(n);
    int srx, sry;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    d[root][0] = fa[root] = root;
    init(root, 1);
    solve();
    dfs(root);
    printf("%d", ans);
    return 0;
}
int lg(int x)
{
    for (int i = 1; ; i++)
    {
        if ((1 << i) > x)
            return i;
    }
}
void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}
void init(int dq, int de)
{
    deep[dq] = de;
    for (int i = 1; i <= lgn; i++)
    {
        d[dq][i] = d[d[dq][i - 1]][i - 1];
    }
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (fa[dq] != b[i].to)
        {
            d[b[i].to][0] = fa[b[i].to] = dq;
            init(b[i].to, de + 1);
        }
    }
}
int lca(int x, int y)
{
    if (deep[x] > deep[y])
    {
        swap(x, y);
    }
    for (int i = lgn; i >= 0; i--)
    {
        if (deep[d[y][i]] >= deep[x])
        {
            y = d[y][i];
        }
    }
    if (x == y)
        return x;
    for (int i = lgn; i >= 0; i--)
    {
        if (d[y][i] != d[x][i])
        {
            y = d[y][i], x = d[x][i];
        }
    }
    return fa[x];
}
void solve()
{
    int srx, sry;
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &srx, &sry);
        int lcxy = lca(srx, sry);
        --pc[lcxy];
        --pc[fa[lcxy]];
        ++pc[srx];
        ++pc[sry];
    }
}
void dfs(int dq)
{
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].to != fa[dq])
        {
            dfs(b[i].to);
            pc[dq] += pc[b[i].to];
        }
    }
    ans = max(ans, pc[dq]);
}

/*
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
*/

By 写pj2017都被吊打的 Cansult