結果

問題 No.399 動的な領主
ユーザー btkbtk
提出日時 2016-07-15 14:12:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 673 ms / 2,000 ms
コード長 4,627 bytes
コンパイル時間 2,159 ms
コンパイル使用メモリ 185,068 KB
実行使用メモリ 43,364 KB
最終ジャッジ日時 2024-11-07 18:32:28
合計ジャッジ時間 8,929 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 36 ms
6,016 KB
testcase_06 AC 638 ms
29,412 KB
testcase_07 AC 647 ms
29,280 KB
testcase_08 AC 667 ms
29,136 KB
testcase_09 AC 624 ms
29,160 KB
testcase_10 AC 5 ms
5,248 KB
testcase_11 AC 27 ms
6,016 KB
testcase_12 AC 451 ms
28,900 KB
testcase_13 AC 430 ms
28,900 KB
testcase_14 AC 195 ms
43,360 KB
testcase_15 AC 242 ms
43,364 KB
testcase_16 AC 302 ms
35,556 KB
testcase_17 AC 673 ms
29,032 KB
testcase_18 AC 644 ms
29,156 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
 
using namespace std;
typedef long long LL;
typedef vector<int> V;
typedef vector<V> Graph;

struct INIT{INIT(){ios::sync_with_stdio(false);cin.tie(0);}}init;

//heavy light decomposition
namespace hld{
#define SZ 120000
    int mem[5][SZ];
};
class HLD{
private:
    int *treesize;
    Graph *tree;
public:
    int size,*group,*id,*par,*bg;
private:
    void setTreeSize(int v){
	treesize[v]=1;
	for(auto &u:(*tree)[v]){
	    setTreeSize(u);
	    treesize[v]+=treesize[u];
	}
    }
    void build(int v,int g,int& i){
	group[v]=g;
	id[v]=i++;
	Graph &gr=(*tree);
	const int sz=gr[v].size();
	if(sz){
	    int h=gr[v][0];
	    for(auto &u:gr[v])
		if(treesize[h]<treesize[u])h=u;
	    build(h,g,i);
	    for(auto &u:gr[v])
		if(h!=u){
		    par[size]=v;
		    bg[size]=i;
		    build(u,size++,i);
		}
	}
    }
public:
    HLD(Graph *tree,int root=0)
	:treesize(hld::mem[0]),
	 tree(tree),size(0),
	 group(hld::mem[1]),
	 id(hld::mem[2]),
	 par(hld::mem[3]),
	 bg(hld::mem[4])
    {
	setTreeSize(root);
	int i=0;
	par[size]=-1;
	bg[size]=i;
	build(root,size++,i);
    }
    using P=pair<int,int>;
    vector<P> decomposition(int r,int c){
	vector<P> res;
	while(group[c]!=group[r]){
	    res.push_back(P(bg[group[c]],id[c]));
	    c=par[group[c]];
	}
	res.push_back(P(id[r],id[c]));
	return res;
    }
};

void make_tree(int v,Graph& G,V& Par,V& D, Graph& C){
    for(auto &e:G[v]){
	if(e!=Par[v]){
	    C[v].push_back(e);
	    D[e]=D[v]+1;
	    Par[e]=v;
	    make_tree(e,G,Par,D,C);
	}
    }
}


//lcaの準備
void build_PP(V& P,vector<V>& PP){
    int N = P.size();
    for(int i = 0; i < N; i++)PP[0][i] = P[i];
    for(int k = 0,f=1;f; k++){
	f=0;
	for(int i = 0; i < N; i++){
	    if(PP[k][i]<0)PP[k+1][i]=-1;
	    else {PP[k+1][i]=PP[k][PP[k][i]];f=1;}
	}
    }
}
int lca(int u,int v,V& D,vector<V> &PP){
    if(D[u] > D[v])swap(u,v);
    for(int k = 0,d;(d=D[v]-D[u]); k++)if((d >> k) & 1)v=PP[k][v];
    if(u==v)return v;
    for(int k = PP.size() - 1; k >=0 ; k--){
        if(PP[k][u]!=PP[k][v]){
            u=PP[k][u];
            v=PP[k][v];
        }
    }
    return PP[0][u];
}


#define SIZE 1000000
#define L(v) (v*2+1)
#define R(v) (v*2+2)
#define SET 0
#define ADD 1
#define GET 2
typedef LL val;
struct node{
    int bg,ed;
    val v,add;
    inline val getval(){
	return v+(1+ed-bg)*add;
    }
    inline void init(int b,int e){
	bg =b,ed=e;
	v=0,add=0;
    }
    bool isleaf(){return bg==ed;}
}mem[SIZE];
inline val comb(val l,val r){
    return l+r;
}
class segTree{
private:
    node *t;
    void make_tree(int bg,int ed,int v=0){
	node *p=t+v;
	p->init(bg,ed);
	if(!p->isleaf()){
	    int m=(bg+ed)/2;
	    make_tree(bg,m,L(v));
	    make_tree(m+1,ed,R(v));
	}
    }
public:
    using P=pair<int,int>;
    segTree(int bg,int ed):t(mem){make_tree(bg,ed);}
    inline void lazy_update(int v){
	node *p=t+v,*l=t+L(v),*r=t+R(v);
	if(p->isleaf())return;
	l->add+=p->add;
	r->add+=p->add;
	p->add=0;
    }
    inline void update(int v){
	node *p=t+v,*l=t+L(v),*r=t+R(v);
	if(p->isleaf()){
	    p->v+=p->add;
	    p->add=0;
	}
	else{
	    p->v=comb(l->getval(),r->getval());
	}
    }
    val treat(int type,int bg,int ed,val x,int v=0){
	node *p=t+v,*l=t+L(v),*r=t+R(v);
	lazy_update(v);
	if(P(bg,ed)==P(p->bg,p->ed)){
	    if(type==ADD)p->add+=x;
	    update(v);
	    return p->getval();
	}
	int m;
	val res=0;
	if(bg<=(m=min(ed,l->ed)))
	    res=comb(res,treat(type,bg,m,x,L(v)));
	if((m=max(bg,r->bg))<=ed)
	    res=comb(res,treat(type,m,ed,x,R(v)));
	update(v);
	return res;
    }
    val get(int bg,int ed){
	return treat(GET,bg,ed,val());
    }
    val add(int bg,int ed,val x){
	//	cout<<"add:"<<bg<<","<<ed<<endl;
	return treat(ADD,bg,ed,x);
    }
};

int main(){
    int N;
    cin>>N;
    Graph g(N+1),child(N+1);
    V depth(N+1,0),par(N+1,-1);
    vector<V> parpar(20,V(N+1,-1));
    g[0].push_back(1);
    for(int i=1;i<N;i++){
	int u,v;
	cin>>u>>v;
	g[u].push_back(v);
	g[v].push_back(u);
    }
    make_tree(0,g,par,depth,child);
    build_PP(par,parpar);
    HLD h(&child);
    segTree st(0,N);
    int Q;
    LL res=0;
    cin>>Q;
    while(Q--){
	int a,b;
	cin>>a>>b;
	int ca=lca(a,b,depth,parpar);
	LL ans=0;
	//cout<<"(a,b,ca)="<<a<<","<<b<<","<<ca<<endl;
	//cout<<"id(a,b,ca)="<<h.id[a]<<","<<h.id[b]<<","<<h.id[ca]<<endl;
	
	auto p=h.decomposition(ca,a);
	auto q=h.decomposition(ca,b);
	auto s=h.decomposition(ca,ca);
	for(auto &it:p)ans+=st.add(it.first,it.second,1ll);
	for(auto &it:q)ans+=st.add(it.first,it.second,1ll);
	ans-=st.get(s[0].first,s[0].second);
	st.add(s[0].first,s[0].second,-1ll);
	//cout<<ans<<endl;
	res+=ans;
    }
    cout<<res<<endl;
}
0