求调(^人^)

P4114 Qtree1

qwerty111111 @ 2024-09-16 10:07:17

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;

int n , m;
int h[N] , tot;
struct node{
    int to , nxt , dis; 
} e[N];

inline void add(int u , int v , int w){
    e[++tot].to = v;
    e[tot].dis = w;
    e[tot].nxt = h[u];
    h[u] = tot;
}

int dep[N] , sze[N] , fa[N] , hson[N] , dfn[N] , iddfn[N] , cnt , A[N] , top[N];
inline void dfs(int x , int f){
    dep[x] = dep[f] + 1 , sze[x] = 1 , fa[x] = f , hson[x] = 0;
    for (int i = h[x] ; i ; i = e[i].nxt){
        int y = e[i].to , w = e[i].dis;
        if(y == f) continue;
        dfs(y , x);
        sze[x] += sze[y];
        if(sze[y] > sze[hson[x]]) hson[x] = y;
    }
}

inline void hld(int x , int topf){
    dfn[x] = ++cnt , iddfn[dfn[x]] = x ; top[x] = topf; 
    if(hson[x]) hld(hson[x] , topf);
    else return;
    for (int i = h[x] ; i ; i = e[i].nxt){
        int y = e[i].to , w = e[i].dis;
        if(y == fa[x] || y == hson[x]) continue;    
        hld(y , y);
        A[dfn[y]] = w;
    } 
}

namespace SegmentTree{
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
    int T[N << 2];

    inline void maintain(int u){
        T[u] = max(T[lc] , T[rc]);  
    }

    inline void Build(int u , int l ,int r){
        if(l == r){
            T[u] = A[l];
            return;
        }
        Build(lc , l , mid) , Build(rc , mid + 1 , r);
        maintain(u);
    }

    inline void Modify(int u , int l , int r , int p , int x){
        if(l == r){
            T[u] = x;
            return;
        }
        if(p <= mid) Modify(lc , l , mid , p , x);
        else Modify(rc , mid + 1 , r , p , x);
        maintain(u);
    }

    inline int Ask(int u , int l , int r , int L , int R){
        if(l >= L && r <= R){
            return T[u];
        }
        if(R <= mid) return (lc , l , mid , L , R);
        if(L > mid) return (rc , mid + 1 , r , L , R);
        return max(Ask(lc , l , mid , L , R) , Ask(rc , mid + 1 , r , L , R));
    }
#undef lc
#undef rc
#undef mid
}

inline int QMax(int u ,int v){
    int res = -0x3f3f3f3f;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u , v);
        res = max(res , SegmentTree::Ask(1 , 1 , n , dfn[top[u]] , dfn[u]));
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u , v);
    res = max(res , SegmentTree::Ask(1 , 1 , n , dfn[u] + 1 , dfn[v]));
    return res;
}

signed main(){
    ios::sync_with_stdio(false) , cin.tie(0);
    cin >> n;
    for (int i = 1 ; i < n ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        add(u , v , w);
        add(v , u , w);
    }   

    dfs(1 , 0) , hld(1 , 1) , SegmentTree::Build(1 , 1 , n);

    string s;
    while(1){
        cin >> s;
        int x , y;
        if(s[0] == 'D') break;
        cin >> x >> y;  
        if(s[0] == 'Q'){
            if(x == y) cout << "0\n";
            else cout << QMax(x , y) << "\n";
        }
        if(s[0] == 'C'){
            x = x * 2 - 1;
            int a = e[x].to , b = e[x + 1].to;
            if(fa[a] == b) x = a;
            else x = b;
            SegmentTree::Modify(1 , 1 , n , dfn[x] , y);
        }
    }

    return 0;
}

by Shunpower @ 2024-09-16 10:46:22

@qwerty111111 马上我看看，你别急

by qwerty111111 @ 2024-09-16 10:47:33

我改完是这样了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;

int n , m;
int h[N] , tot;
struct node{
    int to , nxt , dis; 
} e[N];

inline void add(int u , int v , int w){
    e[++tot].to = v;
    e[tot].dis = w;
    e[tot].nxt = h[u];
    h[u] = tot;
}

int dep[N] , sze[N] , fa[N] , hson[N] , dfn[N] , iddfn[N] , cnt , A[N] , top[N];
inline void dfs(int x , int f){
    dep[x] = dep[f] + 1 , sze[x] = 1 , fa[x] = f , hson[x] = 0;
    for (int i = h[x] ; i ; i = e[i].nxt){
        int y = e[i].to , w = e[i].dis;
        if(y == f) continue;
        dfs(y , x);
        sze[x] += sze[y];
        if(sze[y] > sze[hson[x]]) hson[x] = y;
    }
}

inline void hld(int x , int topf){
    dfn[x] = ++cnt , iddfn[dfn[x]] = x ; top[x] = topf; 
    if(hson[x]) hld(hson[x] , topf);
    else return;
    for (int i = h[x] ; i ; i = e[i].nxt){
        int y = e[i].to , w = e[i].dis;
        if(y == fa[x]){
            continue;
        }
        if(y != hson[x]) hld(y , y);
        A[dfn[y]] = w;
    } 
}

namespace SegmentTree{
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
    int T[N << 2];

    inline void maintain(int u){
        T[u] = max(T[lc] , T[rc]);  
    }

    inline void Build(int u , int l ,int r){
        if(l == r){
            T[u] = A[l];
            return;
        }
        Build(lc , l , mid) , Build(rc , mid + 1 , r);
        maintain(u);
    }

    inline void Modify(int u , int l , int r , int p , int x){
        if(l == r){
            T[u] = x;
            return;
        }
        if(p <= mid) Modify(lc , l , mid , p , x);
        else Modify(rc , mid + 1 , r , p , x);
        maintain(u);
    }

    inline int Ask(int u , int l , int r , int L , int R){
        if(l >= L && r <= R){
            return T[u];
        }
        if(R <= mid) return Ask(lc , l , mid , L , R);
        if(L > mid) return Ask(rc , mid + 1 , r , L , R);
        return max(Ask(lc , l , mid , L , R) , Ask(rc , mid + 1 , r , L , R));
    }
#undef lc
#undef rc
#undef mid
}

inline int QMax(int u ,int v){
    int res = -0x3f3f3f3f;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u , v);
        res = max(res , SegmentTree::Ask(1 , 1 , n , dfn[top[u]] , dfn[u]));
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u , v);
    res = max(res , SegmentTree::Ask(1 , 1 , n , dfn[u] + 1 , dfn[v]));
    return res;
}

signed main(){
    ios::sync_with_stdio(false) , cin.tie(0);
    cin >> n;
    for (int i = 1 ; i < n ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        add(u , v , w);
        add(v , u , w);
    }   

    dfs(1 , 0) , hld(1 , 1) , SegmentTree::Build(1 , 1 , n);

    string s;
    while(1){
        cin >> s;
        int x , y;
        if(s[0] == 'D') break;
        cin >> x >> y;  
        if(s[0] == 'Q'){
            if(x == y) cout << "0\n";
            else cout << QMax(x , y) << "\n";
        }
        if(s[0] == 'C'){
            x = x * 2 - 1;
            int a = e[x].to , b = e[x + 1].to;
            if(fa[a] == b) x = a;
            else x = b;
            SegmentTree::Modify(1 , 1 , n , dfn[x] , y);
        }
    }

    return 0;
}
/*
10
1 2 2
1 4 3
1 5 8
2 3 5
2 6 10
4 7 9
6 9 6
7 8 9
7 10 2
CHANGE 7 8
CHANGE 3 5
QUERY 3 9
CHANGE 2 9
QUERY 3 5
QUERY 1 4
QUERY 4 1
CHANGE 4 2
CHANGE 5 6
DONE
*/

by Shunpower @ 2024-09-16 10:50:15

@qwerty111111 

res = max(res , SegmentTree::Ask(1 , 1 , n , dfn[u] + 1 , dfn[v]));

这个地方，需要特判 dfn[u]==dfn[v]。我猜你会觉得如果一开始 u\ne v 就不存在这种情况了，但是显然，一开始 u\ne v 不代表它们跳完重链之后不会在同一个点上。

by Shunpower @ 2024-09-16 10:52:38

@qwerty111111

你考虑这个：

改了就能过了。

by qwerty111111 @ 2024-09-16 10:54:51

@Shunpower OK 过了过了 感谢dalao orz

by qwerty111111 @ 2024-09-16 11:09:47

@Shunpower 那为啥题解没特判呢

by Rubbish_Du @ 2024-09-16 11:43:27

@qwerty111111 因为题解是对的（bushi）

by Shunpower @ 2024-09-16 11:54:48

@qwerty111111 哪篇

by Shunpower @ 2024-09-16 11:59:21

@qwerty111111 等一下，我刚刚给你发的这个 hack 是不对的。我再看一下

by Shunpower @ 2024-09-16 12:04:05

@qwerty111111 哦，我明白了，是因为你们的线段树写法不一样。

首先这种两个点跳到一个点上的情况肯定是存在的。

题解里面的线段树通过判断 mid 的位置来决定进入哪个区间，然后合并贡献，这样的话对于不合法的 L>R 区间题解不会进入任何一个区间计算贡献，就不会爆炸。但是你的没有考虑到这种不合法情况，两种情况都不符合就会直接进入最后一个 else，导致线段树爆炸。

上一页 | 下一页