FII Code 2021 Round #1 : D. Dr. Anei

TLEに苦しんだけど何とか全完。
https://csacademy.com/contest/fii-code-2021-round-1/task/dranei/

問題

木を成す無向グラフが与えられる。
各点には数値が設定されている。
以下のクエリに順次答えよ。

• 頂点x,yとパラメータzが与えられる。この木をxを根とする木とみなしたとき、yを含むxの子のsubtree内の頂点全体に対し、数値にzを加える。
• 頂点xが与えられるので、現時点での数値を答える。

解法

先にDFS順で頂点を並べ替えよう。
そうすると、前者のクエリはある区間に対する加算になるので、BITを使えば高速に更新できる。
加算対象がどのsubtreeかを求めるパートは、各頂点について、子頂点のindexの最大値を昇順で持っておけば二分探索で求められる。

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> bt;

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

void dfs(int cur,int pre) {
	L[cur]=id++;
	re[L[cur]]=cur;
	bt.add(L[cur],C[cur]);
	bt.add(L[cur]+1,-C[cur]);
	int i;
	FOR(i,E[cur].size()) if(E[cur][i].second==pre) {
		E[cur].erase(E[cur].begin()+i);
		break;
	}
	
	FORR2(v,e,E[cur]) {
		dfs(e,cur);
		v=R[e]-1;
	}
	
	
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>C[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back({0,y-1});
		E[y-1].push_back({0,x-1});
	}
	id=1;
	dfs(0,0);
	
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y>>r;
			
			x--;
			y--;
			if(L[x]<L[y]&&L[y]<R[x]) {
				k=lower_bound(ALL(E[x]),make_pair(L[y],0))-E[x].begin();
				bt.add(L[E[x][k].second],r);
				bt.add(R[E[x][k].second],-r);
				
			}
			else {
				bt.add(0,r);
				bt.add(L[x],-r);
				bt.add(R[x],r);
			}
			
		}
		else {
			cin>>x;
			y=L[x-1];
			cout<<bt(y)<<endl;
		}
	}
		
		
	
}

まとめ

地味にA問題の読解で手間取った。