結果

問題 No.399 動的な領主
ユーザー houren
提出日時 2023-12-07 15:28:12
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 783 ms / 2,000 ms
コード長 4,324 bytes
コンパイル時間 9,496 ms
コンパイル使用メモリ 276,564 KB
最終ジャッジ日時 2025-02-18 08:58:02
ジャッジサーバーID
（参考情報） 		judge4 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/lazysegtree>
using namespace atcoder;
using ll = long long;
using P = pair<ll,ll>;
#define fix(x) fixed << setprecision(x)
#define asc(x) x, vector<x>, greater<x>
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}
constexpr ll INFLL = (1LL << 62), MOD = 998244353;
constexpr int INF = (1 << 30);

// op(S,S): 交換律を満たす二項演算(結合律は未実装)
// Edge: 重みはSであること
// V: Sの配列型 vector<S>を引数に与えると生成されるデータ構造であること
// F: S->Sの関数
// R(V v, int l, int r, F x): 区間[l,r)操作クエリ
// Q(V v, int l, int r): 区間[l,r)演算処理クエリ 返り値の型はSであること
template<class S, S (*op)(S, S), S (*e)(), class Edge, class V, class F, 
         void (*R)(V&, int, int, F), S (*Q)(V&, int, int)>
struct HLD{
    int n, root;
    vector<vector<Edge>> g;
    vector<S> data_;
    V data;
    vector<int> st_size, label, par, top;
    HLD(){}
    HLD(const vector<vector<Edge>>& _g, int r = 0) : 
    n(_g.size()), g(_g), root(r), data_(n), st_size(n,1), label(n), par(n,-1), top(n){
        par[root] = -1;
        dfs_size(root);
        int num = 0;
        dfs_hld(root, num, root);
        data = V(data_);
    }
    void dfs_size(int now){
        for(Edge& edge:g[now]){
            if(par[now]==edge.to) continue;
            par[edge.to] = now;
            dfs_size(edge.to);
            st_size[now] += st_size[edge.to];
            if(st_size[g[now][0].to] < st_size[edge.to]) swap(g[now][0], edge);
        }
    }
    void dfs_hld(int now, int& num, int t){
        label[now] = num, top[now] = t;
        for(Edge& edge:g[now]){
            if(edge.to==par[now]) continue;
            data_[num++] = edge.w;
            dfs_hld(edge.to, num, (edge==g[now][0] ? t : edge.to));
        }
    }
    // {op(u,...,v), lca(u,v)}
    pair<S, int> prod(int u, int v){
        S res = e();
        while(top[u]!=top[v]){
            if(label[u]>label[v]){
                res = op(res, Q(data, label[top[u]] - (top[u]!=root), label[u]));
                u = (top[u]!=root ? par[top[u]] : top[u]);
            }else{
                res = op(res, Q(data, label[top[v]] - (top[v]!=root), label[v]));
                v = (top[v]!=root ? par[top[v]] : top[v]);
            }
        }
        res = op(res, (label[u]<label[v] ? Q(data, label[u], label[v]) : Q(data, label[v], label[u])));
        return {res, (label[u]<label[v] ? u : v)};
    }
    // 列操作クエリ
    int apply(int u, int v, F x){
        if(label[u]<label[v]) swap(u,v);
        while(top[u]!=top[v]){
            R(data, label[top[u]] - (top[u]!=root), label[u], x);
            u = (top[u]!=root ? par[top[u]] : top[u]);
            if(label[u]<label[v]) swap(u,v);
        }
        R(data, label[v], label[u], x);
        return v;
    }
};

struct S{
    ll val, siz;
    S(ll a, ll b){ val = a, siz = b; }
    S(){ val = 0, siz = 1; }
};
S op(S a, S b){ return {a.val+b.val, a.siz+b.siz}; }
S e(){ return S(0,1); }
S mapping(ll x, S a){ return {a.val+a.siz*x, a.siz}; }
ll composition(ll x, ll y){ return x+y; }
ll id(){ return 0; }
using SEG = lazy_segtree<S,op,e,ll,mapping,composition,id>;
struct Edge{
    int to; S w;
    bool operator==(Edge& edge){ return to==edge.to; }
};
void R(SEG& seg, int l, int r, ll x){ seg.apply(l,r,x); }
S Q(SEG& seg, int l, int r){ return seg.prod(l,r); }
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<Edge>> g(n);
    rep(i,n-1){
        int u,v;
        cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v,S(0,1));
        g[v].emplace_back(u,S(0,1));
    }
    HLD<S,op,e,Edge,SEG,ll,R,Q> hld(g);
    int q;
    cin >> q;
    ll ans = 0, t = 0;
    while(q--){
        int u,v;
        cin >> u >> v;
        u--; v--;
        int r = hld.apply(u,v,1);
        if(r) hld.apply(r,hld.par[r],1);
        else t++;
        ans += hld.prod(u,v).first.val;
        if(r) ans += hld.prod(r,hld.par[r]).first.val;
        else ans += t;
    }
    cout << ans << '\n';
    return 0;
}
0