結果

問題 No.235 めぐるはめぐる (5)
ユーザー btkbtk
提出日時 2016-07-18 16:08:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,041 ms / 10,000 ms
コード長 5,342 bytes
コンパイル時間 1,987 ms
コンパイル使用メモリ 183,096 KB
実行使用メモリ 61,780 KB
最終ジャッジ日時 2024-04-23 16:29:32
合計ジャッジ時間 10,207 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,041 ms
61,780 KB
testcase_01 AC 1,408 ms
59,716 KB
testcase_02 AC 1,874 ms
60,812 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 200010
    int mem[4][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[0]),
	 par(hld::mem[2]),
	 bg(hld::mem[3])
    {
	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 900000
#define L(v) (v*2+1)
#define R(v) (v*2+2)
#define SET 0
#define ADD 1
#define GET 2

typedef LL val;
const LL MOD=1e9+7;
struct node{
    int bg,ed;
    val v,add,sum;
    inline val getval(){
	return (v+sum*add%MOD)%MOD;
    }
    inline void init(int b,int e){
	bg =b,ed=e;
	v=0,add=0,sum=0;
    }
    bool isleaf(){return bg==ed;}
}mem[SIZE];
inline val comb(val l,val r){
    return (l+r)%MOD;
}
class segTree{
private:
    node *t;
    val make_tree(int bg,int ed,vector<int> &c,vector<int> &s,int v=0){
	node *p=t+v;
	p->init(bg,ed);
	if(!p->isleaf()){
	    int m=(bg+ed)/2;
	    p->sum+=make_tree(bg,m,c,s,L(v));
	    p->sum+=make_tree(m+1,ed,c,s,R(v));
	    p->sum%=MOD;
	    update(v);
	}
	else{
	    p->sum=c[bg];
	    p->v=s[bg];
	}
	return p->sum;
    }
public:
    using P=pair<int,int>;
    segTree(int bg,int ed,vector<int> &c,vector<int> &s):t(mem){
	make_tree(bg,ed,c,s);
    }
    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)%=MOD;
	(r->add+=p->add)%=MOD;
	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->sum%MOD;
	    p->v%=MOD;
	    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)%=MOD;
	    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){
	return treat(ADD,bg,ed,x);
    }
};
const int root=0;
int main(){
    int N;cin>>N;
    N++;
    vector<int> s(N),S(N),c(N),C(N);
    s[root]=c[root]=0;
    for(int i=1;i<N;i++)cin>>s[i];
    for(int i=1;i<N;i++)cin>>c[i];
    Graph g(N),tree(N);
    g[root].push_back(1);
    V par(N,-1),depth(N,0);
    vector<V> pp(18,V(N,-1));
    for(int i=2;i<N;i++){
	int a,b;
	cin>>a>>b;
	g[a].push_back(b);
	g[b].push_back(a);
    }
    make_tree(root,g,par,depth,tree);
    build_PP(par,pp);
    HLD hld(&tree,root);
    for(int i=0;i<N;i++){
	S[hld.id[i]]=s[i];
	C[hld.id[i]]=c[i];
    }
    segTree st(0,N-1,C,S);
    int Q;
    cin>>Q;
    while(Q--){
	int t;
	cin>>t;
	if(t){
	    int x,y;
	    cin>>x>>y;
	    int ca=lca(x,y,depth,pp);
	    LL ans=0;
	    auto p=hld.decomposition(ca,x);
	    auto q=hld.decomposition(ca,y);
	    auto r=hld.decomposition(ca,ca);
	    for(auto &it:p)(ans+=st.get(it.first,it.second))%=MOD;
	    for(auto &it:q)(ans+=st.get(it.first,it.second))%=MOD;
	    for(auto &it:r)ans+=MOD-st.get(it.first,it.second);
	    cout<<ans%MOD<<endl;
	}
	else{
	    int x,y,z;
	    cin>>x>>y>>z;
	    int ca=lca(x,y,depth,pp);
	    auto p=hld.decomposition(ca,x);
	    auto q=hld.decomposition(ca,y);
	    auto r=hld.decomposition(ca,ca);
	    for(auto &it:p)st.add(it.first,it.second,z);
	    for(auto &it:q)st.add(it.first,it.second,z);
	    for(auto &it:r)st.add(it.first,it.second,MOD-z);
	}
    }
    return 0;
}
0