提出 #76518070

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define pb push_back
//#define int long long 
typedef long long ll;
typedef __int128 LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;

int n;
vector<int> G[100005];
int euler_dfn[200005];
int first_pos[100005], tim, dep[100005], fa[100005];
int st[200005][22];
int Log2[200005];
void dfs(int u, int father){
    fa[u] = father;
    dep[u] = dep[father] + 1;
    euler_dfn[++tim] = u;
    first_pos[u] = tim;
    for(auto v : G[u]){
        if(v == father) continue;
        dfs(v, u);
        euler_dfn[++tim] = u;
    }
}
int Min(int x, int y){
    return dep[x] < dep[y] ? x : y;
}
int lca(int u, int v){ // O(1)
    int l = first_pos[u], r = first_pos[v];
    if(l > r) swap(l, r);
    int k = Log2[r - l + 1];
    return Min(st[l][k], st[r - (1<<k) + 1][k]);
}
void prework(){
    dfs(1, 0);
    for(int i = 1; i <= tim; i ++){
        st[i][0] = euler_dfn[i];
        if(i > 1) Log2[i] = Log2[i>>1] + 1;
    }
    for(int j = 1; j <= 21; j ++){
        for(int i = 1; i + (1<<j) - 1 <= tim; i ++){
            st[i][j] = Min(st[i][j - 1], st[i + (1<<(j-1))][j - 1]);
        }
    }
}

bool hve[100005];
struct SegmentTree{
    #define lc p<<1
    #define rc p<<1|1

    struct Node{
        int l, r;
        int u, v;
    }tr[100005<<2];

    int distance(int u, int v){
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    pii get(int a, int b, int c, int d){
        array<int,4> arr = {a, b, c, d};
        int u = -1, v = -1;
        int max_dis = -1;
        for(int i = 0; i < 4; i ++){
            for(int j = i + 1; j < 4; j ++){
                if(arr[i] == -1 || arr[j] == -1) continue;
                int dis = distance(arr[i], arr[j]);
                if(max_dis < dis){
                    max_dis = dis;
                    u = arr[i], v = arr[j];
                }
            }
        }
        return make_pair(u, v);
    }

    void _pushup(int p){
        auto [x, y] = get(tr[lc].u, tr[lc].v, tr[rc].u, tr[rc].v);
        tr[p].u = x; tr[p].v = y;
    }

    void build(int p, int l, int r){
        tr[p] = {l, r, l, l};
        if(l == r) return;
        int mid = l + r >> 1;
        build(lc, l, mid); build(rc, mid + 1, r);
        _pushup(p);
    }

    void update(int p, int x){
        if(tr[p].l == tr[p].r){
            if(hve[x]){
                tr[p].u = tr[p].v = -1;
            }
            else{
                tr[p].u = tr[p].v = x;
            }
            hve[x] ^= 1;
            return;
        }
        int mid = tr[p].l + tr[p].r >> 1;
        if(x <= mid) update(lc, x);
        else update(rc, x);
        _pushup(p);
    }

    Node query(int p, int l, int r){
        if(l <= tr[p].l && tr[p].r <= r){
            return tr[p];
        }
        int mid = tr[p].l + tr[p].r >> 1;
        if(r <= mid) return query(lc, l, r);
        if(l > mid) return query(rc, l, r);
        Node lson = query(lc, l, r), rson = query(rc, l, r);
        Node t;
        t.l = lson.l; 
        t.r = rson.r;
        auto [x, y] = get(lson.u, lson.v, rson.u, rson.v);
        t.u = x; t.v = y;
        return t;
    }

}seg;

void solve()
{
    cin >> n;
    for(int i = 1; i <= n - 1; i ++){
        int u, v;
        cin >> u >> v;
        G[u].pb(v); G[v].pb(u);
    }
    prework();
    for(int i = 1; i <= n; i ++) hve[i] = true;
    seg.build(1, 1, n);
    int q;
    cin >> q;
    while(q --){
        int u;
        cin >> u;
        seg.update(1, u);
        auto [_, _, a, b] = seg.tr[1];
        cout << seg.distance(a, b) << "\n";
    }
}


signed main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // int T=1; cin>>T; while(T--)
    solve();
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In member function 'void SegmentTree::build(int, int, int)':
./Main.cpp:93:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid = l + r >> 1;
      |                   ~~^~~
./Main.cpp: In member function 'void SegmentTree::update(int, int)':
./Main.cpp:109:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         int mid = tr[p].l + tr[p].r >> 1;
      |                   ~~~~~~~~^~~~~~~~~
./Main.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int)':
./Main.cpp:119:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |         int mid = tr[p].l + tr[p].r >> 1;
      |                   ~~~~~~~~^~~~~~~~~
./Main.cpp: In function 'void solve()':
./Main.cpp:150:18: warning: name-independent declarations only available with '-std=c++2c' or '-std=gnu++2c' [-Wc++26-extensions]
  150 |         auto [_, _, a, b] = seg.tr[1];
      |                  ^

ジャッジ結果