kmjp's blog

競技プログラミング参加記です

yukicoder : No.900 aδδitivee

これはあまり方針に迷わなかった。
https://yukicoder.me/problems/no/900

問題

根付き木が与えられる。
各辺には、長さが設定されている。

以下のクエリに順次答えよ。

  • 頂点aのSubTree内の全辺に、長さをxずつ加算する
  • 根頂点から頂点bへの長さを答える

解法

頂点vの根頂点からの距離をF(v)とし、(辺の長さを1とみなしたときの)頂点vの根からの深さをD(v)とする。
頂点aに対し前者のクエリを適用すると、SubTree内の頂点xに対してはF(x)はx*(D(v)-D(a))だけ加算される。
よって、F(v)をD(v)の1次関数とみなし、F(v)=A(v)*D(v)+B(v)としよう。

事前にオイラーツアーを行い頂点を並べ替えておくと、前者のクエリは区間に対しA(v)とB(v)に同じ値を加減算することになるので、A(v)とB(v)それぞれBITを持っておけばよい。

int N,Q;
vector<pair<int,int>> E[101010];
ll D[101010];
int L[101010],R[101010];
int id;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bta,btb;

void dfs(int cur,int pre,int d) {
	D[cur]=d;
	
	L[cur]=id++;
	FORR(e,E[cur]) if(e.first!=pre) {
		int pa=id;
		dfs(e.first,cur,d+1);
		bta.add(pa,e.second);
		bta.add(id,-e.second);
	}
	R[cur]=id;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		E[x].push_back({y,r});
		E[y].push_back({x,r});
	}
	dfs(0,0,0);
	
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y;
			btb.add(L[x],y);
			btb.add(R[x],-y);
			bta.add(L[x],-D[x]*y);
			bta.add(R[x],D[x]*y);
			
		}
		else {
			cin>>x;
			cout<<bta(L[x])+D[x]*btb(L[x])<<endl;
		}
	}
}

まとめ

区間加算の累積和問題は、SegTreeよりBIT派かな…。