結果

問題 No.386 貪欲な領主
ユーザー koprickykopricky
提出日時 2017-08-02 17:52:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 449 ms / 2,000 ms
コード長 4,508 bytes
コンパイル時間 2,115 ms
コンパイル使用メモリ 168,308 KB
実行使用メモリ 28,960 KB
最終ジャッジ日時 2024-10-11 05:57:04
合計ジャッジ時間 5,023 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,760 KB
testcase_01 AC 3 ms
5,760 KB
testcase_02 AC 4 ms
5,760 KB
testcase_03 AC 3 ms
5,888 KB
testcase_04 AC 449 ms
28,960 KB
testcase_05 AC 367 ms
21,148 KB
testcase_06 AC 361 ms
20,924 KB
testcase_07 AC 6 ms
5,888 KB
testcase_08 AC 45 ms
7,296 KB
testcase_09 AC 9 ms
5,760 KB
testcase_10 AC 4 ms
5,760 KB
testcase_11 AC 4 ms
5,888 KB
testcase_12 AC 5 ms
5,760 KB
testcase_13 AC 11 ms
6,144 KB
testcase_14 AC 372 ms
21,068 KB
testcase_15 AC 332 ms
28,700 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;

vector<int> G[MAX_N];
vector<int> ord;
vector<int> vec;
vector<int> val;
int depth[MAX_N];
int id[MAX_N];
int id2[MAX_N];
bool flag[MAX_N];

//インデックスは0始まり
//最小値を求めるプログラム(RMQ)
const int N = 1 << 18;	//10^5程度

//セグメント木を持つグローバル配列

int n_;
int dat[2*N-1];
int idx[2*N-1];

//初期化
//n_はx以上の最小の2のべき乗
void init(int x)
{
	//簡単のため、要素数を2のべき乗に
	n_=1;
	while(n_<x){
		n_*=2;
	}
	rep(i,2*n_-1){
		dat[i] = INF;
        idx[i] = -1;
	}
}

//k番目の値をaに変更する
void update(int k,int a)
{
	//葉の節点
	k += n_-1;
	dat[k] = a;
    idx[k] = k - (n_-1);
	//登りながら更新
	while(k>0){
		k = (k-1)/2;
		if(dat[2*k+1] < dat[2*k+2]){
            dat[k] = dat[2*k+1];
            idx[k] = idx[2*k+1];
        }else{
            dat[k] = dat[2*k+2];
            idx[k] = idx[2*k+2];
        }
	}
}

P query(int a,int b,int k=0,int l=0,int r=n_)
{
	if(r <= a || b <= l){
		return P(INF,-1);
	}
	if(a <= l && r <= b){
		return P(dat[k],idx[k]);
	}else{
		P vl = query(a,b,2*k+1,l,(l+r)/2);
		P vr = query(a,b,2*k+2,(l+r)/2,r);
		return min(vl,vr);
	}
}

void dfs(int u,int k)
{
    id[u] = (int)ord.size();
    id2[u] = (int)vec.size();
    ord.pb(u);
    vec.pb(val[u]);
    flag[u] = true;
    depth[u] = k;
    rep(i,G[u].size()){
        if(!flag[G[u][i]]){
            dfs(G[u][i],k+1);
            ord.pb(u);
        }
    }
    vec.pb(-val[u]);
}

template<class V> class segtree {
private:
    int n,sz;
    vector<V> node, lazy;

public:
    segtree(vector<V> v) {
        sz = (int)v.size();
        n = 1;
        while(n < sz){
            n *= 2;
        }
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);
        rep(i,sz){
            node[i+n-1] = v[i];
        }
        for(int i=n-2; i>=0; i--){
            node[i] = node[i*2+1] + node[i*2+2];
        }
    }
    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void range(int a, int b, V x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            range(a, b, x, 2*k+1, l, (l+r)/2);
            range(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }
    V query(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a){
            return 0;
        }
        if(a <= l && r <= b){
            return node[k];
        }
        V vl = query(a, b, 2*k+1, l, (l+r)/2);
        V vr = query(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
    void print()
    {
        rep(i,sz){
            cout << query(i,i+1) << " ";
        }
        cout << endl;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    val.resize(n);
    rep(i,n){
        cin >> val[i];
    }
    dfs(0,0);
    init(ord.size());
    rep(i,ord.size()){
        update(i,depth[ord[i]]);
    }
    segtree<int> sg(vec);
    int q;
    cin >> q;
    ll ans = 0;
    rep(i,q){
        int a,b,c;
        cin >> a >> b >> c;
        int lca = ord[query(min(id[a],id[b]),max(id[a],id[b])+1).se];
        int sm = sg.query(min(id2[a],id2[lca]),max(id2[a],id2[lca])+1) + sg.query(min(id2[b],id2[lca]),max(id2[b],id2[lca])+1);
        sm -= val[lca];
        ans += (ll)sm*c;
    }
    cout << ans << endl;
    return 0;
}
0