#386657 (C++14) No.898 tri-βutree

提出ソース

結果

問題	No.898 tri-βutree
ユーザー	ferin
提出日時	2019-10-04 21:52:28
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,179 bytes
コンパイル時間	2,058 ms
コンパイル使用メモリ	192,836 KB
実行使用メモリ	35,452 KB
最終ジャッジ日時	2024-10-03 07:30:25
合計ジャッジ時間	8,574 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	191 ms 35,452 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
	out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
	out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

struct HLDecomposition {
    int n, pos;
    vector<vector<ll>> g;
    vector<ll> vid,   // HL分解後のグラフでのid
        head,  // 頂点が属するheavy-pathのheadのid
        sub,   // 部分木のサイズ
        hvy,   // heavy-path上での次の頂点のid
        par,   // 親のid
        depth, // 深さ
        inv,   // HL分解前のグラフのid（添え字が分解後のid）
        type,  // 森をHL分解するときの属する木の番号
        ps,    // 行きがけ順
        pt;    // 帰りがけ順

    // 根rtからdfsして部分木の大きさ、heavy-edgeの判定などをする
    void dfs1(ll rt) {
        stack<PII> st;
        par[rt] = -1;
        depth[rt] = 0;
        st.emplace(rt, 0);
        while(st.size()) {
            ll v = st.top().first;
            ll &i = st.top().second;
            if(i < (ll)g[v].size()) {
                ll u = g[v][i++];
                if(u == par[v]) continue;
                par[u] = v;
                depth[u] = depth[v]+1;
                st.emplace(u, 0);
            } else {
                st.pop();
                for(ll &u: g[v]){
                    if(u == par[v]) swap(u, g[v].back());
                    if(u == par[v]) continue;
                    sub[v] += sub[u];
                    if(sub[u]>sub[g[v].front()]) swap(u, g[v].front());
                }
            }
        }
    }
    // 根r、c番目の木についてchainについての情報をまとめる
    void dfs2(ll r, ll c) {
        using T = tuple<ll, ll, ll>;
        stack<T> st;
        st.emplace(r,r,0);
        while(!st.empty()) {
            ll v,h;
            tie(v,h,ignore)=st.top();
            ll &i=get<2>(st.top());
            if(!i) {
                type[v]=c;
                ps[v]=vid[v]=pos++;
                inv[vid[v]]=v;
                head[v]=h;
                hvy[v]=(g[v].empty()?-1:g[v][0]);
                if(hvy[v]==par[v]) hvy[v]=-1;
            }
            if(i<(ll)g[v].size()) {
                ll u=g[v][i++];
                if(u==par[v]) continue;
                st.emplace(u,(hvy[v]==u?h:u),0);
            } else {
                st.pop();
                pt[v]=pos;
            }
        }
    }

    HLDecomposition(){}
    HLDecomposition(ll sz):
        n(sz), pos(0), g(n),
        vid(n,-1), head(n), sub(n,1), hvy(n,-1),
        par(n), depth(n), inv(n), type(n), ps(n), pt(n) {}

    void add_edge(ll u, ll v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void build(vector<ll> rs=vector<ll>(1,0)) {
        ll c=0;
        for(ll r: rs) {
            dfs1(r);
            dfs2(r, c++);
        }
    }

    // 頂点に対する処理 [u,v] 開区間なので注意!!!
    void for_each(ll u, ll v, const function<void(ll,ll)>& f) {
        while(1){
            if(vid[u]>vid[v]) swap(u,v);
            // [max(vid[head[v]],vid[u]), vid[v]] の区間についての操作を行う
            f(max(vid[head[v]], vid[u]), vid[v]);
            if(head[u]!=head[v]) v = par[head[v]];
            else break;
        }
    }
    // 辺に対する処理 [u,v] 開区間なので注意!!!
    void for_each_edge(ll u, ll v, const function<void(ll,ll)>& f) {
        while(1) {
            if(vid[u]>vid[v]) swap(u,v);
            if(head[u]!=head[v]) {
                f(vid[head[v]], vid[v]);
                v = par[head[v]];
            } else {
                if(u!=v) f(vid[u]+1, vid[v]);
                break;
            }
        }
    }
    ll lca(ll u, ll v) {
        while(1) {
            if(vid[u]>vid[v]) swap(u,v);
            if(head[u]==head[v]) return u;
            v = par[head[v]];
        }
    }
    ll distance(ll u, ll v) {
        return depth[u] + depth[v] - 2*depth[lca(u,v)];
    }
};
/*
パスu-vの頂点属性クエリ → hld.for_each(u, v, f)
パスu-vの辺属性クエリ → hld.for_each_edge(u, v, f)
頂点vの部分木に対するクエリ → 区間[hld.vid[u]+1, hld.vid[u] + hld.sub[u]) に操作
*/

signed main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll n;
	cin >> n;
	vector<vector<PII>> g(n);
	HLDecomposition hld(n);
	REP(i, n-1) {
		ll a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
		hld.add_edge(a, b);
	}
	hld.build();
	
	vector<ll> dist(n);
	function<void(ll,ll)> dfs = [&](ll v, ll p) {
		for(auto to: g[v]) {
			if(to.first == p) continue;
			dist[to.first] = dist[v] + to.second;
			dfs(to.first, v);
		}
	};
	dfs(0, -1);

	ll q;
	cin >> q;
	while(q--) {
		ll x, y, z;
		cin >> x >> y >> z;

		ll ret = dist[x] + dist[y] + dist[z];
		ret -= dist[hld.lca(x, y)];
		ret -= dist[hld.lca(x, z)];
		ret -= dist[hld.lca(y, z)];
		ll lca = hld.lca(hld.lca(x, y), z);
		ret += dist[lca];
		cout << ret << endl;
	}

	return 0;
}

yukicoder

結果

テストケース

ソースコード