…菜到一定程度了…

我怎么这么菜…

HN大爷都太神了 Orzz

懵逼的 题目

点击确认: Cansult太菜了

扯淡的 题解

一开始看错题了…看成是出错的服务器能影响到的路径最大值了…

Emmm…区间修改, 区间撤回, 单点取$\max$…

标记永久化啊…把标记设成一个堆, 然后再搞一个set记录哪些标记被撤回过好咯

然后看了看ljh_2000大佬的blog, 学习了一个写法, 感觉比较资瓷啊:

每一个线段树搞两个大根堆, 一个表示修改的标记, 一个表示撤回的标记

如果两个堆顶的元素相同, 就把两个堆都弹出, 这样就可以维护带撤回的最大值了

然后写写写…艹我又双叒叕看错题了…

Emmm…不受影响的…那我查询剩下的部分就好了嘛 ←沙茶

然后重写了一个区间查询的版本…

…等等…不对劲啊…

Emmmmmmm…那咋搞啊…

啊! 直接修改路径的补集不就可以了嘛! 怎么修改路径的补集啊…

啊! 我把整棵树都赋成要修改的值, 然后在链上撤回不就好了嘛!

写写写…

等等…你都标记永久化了…怎么在子区间撤回啊…

然后看题解

哦…我真傻, 真的

把树链剖分每次跳的两个端点记录下来

然后按照端点排序, 把两个区间之间的部分修改了就好了

沙茶的 代码

/**************************************************************
    Problem: 4538
    User: Cansult
    Language: C++
    Result: Accepted
    Time:10816 ms
    Memory:73352 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define MAXN (100000 + 5)
#define MAXQ (200000 + 5)
#define pii pair<int, int>
const int root = 1;
using namespace std;
struct tnode
{
    int deep, fa, top, hs, size, begin, end;
}ta[MAXN];
int cnta, n;
struct que
{
    int x, y, z;
}sr[MAXQ];
struct edg
{
    int from, to, next;
}tb[MAXN << 1];
int tg[MAXN], cntt = -1;
struct cmp
{
    bool operator () (const int x, const int y)
    { return x < y; }
};
struct node
{
    int le, ri;
    priority_queue<int, vector<int>, cmp> qwq[2];
}b[MAXN << 2];
pii a[MAXN];
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    b[dq].qwq[0].push(-1);
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh, int e)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].qwq[e].push(zh);
        while (!b[dq].qwq[0].empty() && !b[dq].qwq[1].empty() && b[dq].qwq[0].top() == b[dq].qwq[1].top())
            b[dq].qwq[0].pop(), b[dq].qwq[1].pop();
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        xg(RS(dq), le, ri, zh, e);
    else if (ri <= mi)
        xg(LS(dq), le, ri, zh, e);
    else
        xg(LS(dq), le, mi, zh, e), xg(RS(dq), mi + 1, ri, zh, e);
}
int cx(int dq, int wz)
{
    int re = b[dq].qwq[0].top();
    if (b[dq].le == b[dq].ri)
        return re;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (wz > mi)
        return max(re, cx(RS(dq), wz));
    else
        return max(re, cx(LS(dq), wz));
}
void adn(int from, int to)
{
    tb[++cntt].next = tg[from];
    tb[cntt].from = from;
    tb[cntt].to = to;
    tg[from] = cntt;
}
void init(int dq, int deep)
{
    ta[dq].deep = deep;
    ta[dq].size = 1;
    for (int i = tg[dq]; ~i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            init(tb[i].to, deep + 1);
            ta[dq].size += ta[tb[i].to].size;
            if (ta[tb[i].to].size >= ta[ta[dq].hs].size)
                ta[dq].hs = tb[i].to;
        }
}
void dfs(int dq)
{
    ta[dq].begin = ++cnta;
    if (ta[dq].hs)
        ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
    for (int i = tg[dq]; ~i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
            ta[tb[i].to].top = tb[i].to, dfs(tb[i].to);
    ta[dq].end = cnta;
}
void solve(int x, int y, int zh, int e)
{
    /*puts("\n------------");
    printf("x: %d\ty: %d\tzh: %d\te: %d\n", x, y, zh, e);*/

    int cnt = 0;
    while (ta[x].top != ta[y].top)
    {
        if (ta[ta[x].top].deep < ta[ta[y].top].deep)
            swap(x, y);
        a[++cnt] = make_pair(ta[ta[x].top].begin, ta[x].begin);
        x = ta[ta[x].top].fa;
    }
    if (ta[x].deep > ta[y].deep)
        swap(x, y);
    a[++cnt] = make_pair(ta[x].begin, ta[y].begin);
    sort(a + 1, a + cnt + 1);

    /*for (int i = 1; i <= cnt; i++)
        printf("%d\t%d\n", a[i].first, a[i].second);
    puts("----------------------");*/

    if (a[1].first > 1)
        xg(1, 1, a[1].first - 1, zh, e);
    if (a[cnt].second < n)
        xg(1, a[cnt].second + 1, n, zh, e);
    for (int i = 2; i <= cnt; i++)
        if (a[i - 1].second + 1 <= a[i].first - 1)
            xg(1, a[i - 1].second + 1, a[i].first - 1, zh, e);
}
int main()
{
    memset(tg, -1, sizeof(tg));
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 1, srx, sry; i < n; i++)
        scanf("%d%d", &srx, &sry), adn(srx, sry), adn(sry, srx);
    ta[root].top = ta[root].fa = root;
    init(root, 1);
    dfs(root);
    js(1, 1, n);
    for (int i = 1, sre, srx; i <= q; i++)
    {
        scanf("%d", &sre);
        if(sre == 0)
            scanf("%d%d%d", &sr[i].x, &sr[i].y, &sr[i].z), solve(sr[i].x, sr[i].y, sr[i].z, 0);
        else if (sre == 1)
            scanf("%d", &srx), solve(sr[srx].x, sr[srx].y, sr[srx].z, 1);
        else if (sre == 2)
            scanf("%d", &srx), printf("%d\n", cx(1, ta[srx].begin));
    }
    return 0;
}

/*
13 23
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
6 10
6 11
7 12
7 13
2 1
0 8 13 3
0 9 12 5
2 9
2 8
2 2
0 10 12 1
2 2
1 3
2 7
2 1
0 9 5 6
2 4
2 5
1 7
0 9 12 4
0 10 5 7
2 1
2 4
2 12
1 2
2 5
2 3
*/

By 超级无敌大sb Cansult