萌新刚学OI1ms，全WA求调，悬关

P4114 Qtree1

lihongqian__int128 @ 2024-07-17 21:13:09

#include <bits/stdc++.h>
#define fr first
#define sc second
using namespace std ;
const int N = 1e5 + 5 ;
int n , x[N] , y[N] , w[N] , val ;
string op ;
int tree[N << 2] ;
int fa[N] , dep[N] , siz[N] , son[N] , top[N] , dfn[N] , rnk[N] , cnt , a[N] ;
vector <pair <int , int> > v[N] ;
void pushup(int cur)
{
    tree[cur] = max(tree[cur * 2] , tree[cur * 2 + 1]) ;
    return ;
}
void build(int cur , int lt , int rt)
{
    if(lt == rt)
    {
        tree[cur] = a[lt] ;
        return ;
    }
    int mid = (lt + rt) >> 1 ;
    build(cur * 2 , lt , mid) ;
    build(cur * 2 + 1 , mid + 1 , rt) ;
    pushup(cur) ;
    return ;
}
int query(int cur , int lt , int rt , int qx , int qy)
{
    if(rt < qx || lt > qy)  return 0 ;
    if(lt >= qx && rt <= qy)    return tree[cur] ;
    int mid = (lt + rt) >> 1 ;
    return max(query(cur * 2 , lt , mid , qx , qy) , query(cur * 2 + 1 , mid + 1 , rt , qx , qy)) ;
}
void update(int cur , int lt , int rt , int qx , int qy , int val)
{
    if(rt < qx || lt > qy)  return ;
    if(lt >= qx && rt <= qy)
    {
        tree[cur] = val ;
        return ;
    }
    int mid = (lt + rt) >> 1 ;
    update(cur * 2 , lt , mid , qx , qy , val) ;
    update(cur * 2 + 1 , mid + 1 , rt , qx , qy , val) ;
    pushup(cur) ;
    return ;
}
void dfs1(int cur , int f)
{
    son[cur] = -1 , siz[cur] = 1 ;
    for(int i = 0 ; i < v[cur].size() ; i++)
    {
        int to = v[cur][i].fr ;
        if(to == f) continue ;
        dep[to] = dep[cur] + 1 , fa[to] = cur ;
        a[to] = v[cur][i].sc ;
        dfs1(to , cur) ;
        siz[cur] += siz[to] ;
        if(son[cur] == -1 || siz[to] > siz[son[cur]])   son[cur] = to ;
    }
    return ;
}
void dfs2(int cur , int t)
{
    top[cur] = t , cnt++ , dfn[cur] = cnt , rnk[cnt] = cur ;
    if(son[cur] == -1)  return ;
    dfs2(son[cur] , t) ;
    for(int i = 0 ; i < v[cur].size() ; i++)
    {
        int to = v[cur][i].fr ;
        if(to == fa[cur] || to == son[cur]) continue ;
        dfs2(to , to) ;
    }
    return ;
}
int lca(int x , int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]])   swap(x , y) ;
        x = fa[top[x]] ;
    }
    return (dep[x] < dep[y] ? x : y) ;
}
int main()
{
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;
    cin >> n ;
    for(int i = 1 ; i < n ; i++)    cin >> x[i] >> y[i] >> w[i] , v[x[i]].push_back({y[i] , w[i]}) , v[y[i]].push_back({x[i] , w[i]}) ;
    dfs1(1 , 0) ;
    dfs2(1 , 1) ;
    build(1 , 1 , n) ;
    while(cin >> op)
    {
        if(op == "DONE")    return 0 ;
        if(op == "CHANGE")
        {
            int i , t ;
            cin >> i >> t ;
            if(fa[x[i]] == y[i])    update(1 , 1 , n , dfn[x[i]] , dfn[x[i]] , t) ;
            else    update(1 , 1 , n , dfn[y[i]] , dfn[y[i]] , t) ;
        }
        else
        {
            int l , r , ans = 0 ;
            cin >> l >> r ;
            if(l == r)
            {
                cout << "0\n" ;
                continue ;
            }
            int t = lca(l , r) ;
            while(top[l] != top[t])
            {
                ans = max(ans , query(1 , 1 , n , dfn[top[l]] , dfn[l])) ;
                l = fa[top[l]] ;
            }
            ans = max(ans , query(1 , 1 , n , dfn[t] + 1 , dfn[l])) ;
            while(top[r] != top[t])
            {
                ans = max(ans , query(1 , 1 , n , dfn[top[r]] , dfn[r])) ;
                r = fa[top[r]] ;
            }
            ans = max(ans , query(1 , 1 , n , dfn[t] + 1 , dfn[r])) ;
            cout << ans << '\n' ;
        }
    }
    return 0 ;
}

by lihongqian__int128 @ 2024-07-17 21:24:19

错误 1：

if(lt == rt)
{
  tree[cur] = a[lt] ;
  return ;
}

应该为

if(lt == rt)
{
  tree[cur] = a[dfn[lt]] ;
  return ;
}

但还是错了。

by crz_qwq @ 2024-07-18 08:32:20

Cu ball，我也挂了

by yhylivedream @ 2024-07-18 09:06:23

@crz_qwq @lihongqian__int128 YZ这么恐怖，小6已经学树剖了%%%

by yangyafan @ 2024-07-19 16:48:03

建议用下调试并输出中间结果看看

by tzhengqing @ 2024-07-19 16:49:01

您可以尝试输出中间变量或参考题解改一改(

by tzhengqing @ 2024-07-19 16:49:16

您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(您可以尝试输出中间变量或参考题解改一改(

by yangyafan @ 2024-07-19 16:49:43

您可以尝试输出中间变量或参考题解改一改(大雾

by yangyafan @ 2024-07-19 16:51:23

MN就是NB，看不懂一点

by yangpafan @ 2024-07-20 15:23:11