https://atcoder.jp/contests/abc187/tasks/abc187_e
は木DP解が適切ですが、オイラーツアーでたどる経路を使った区間和計算でも解けます。この考察過程を記録がてら記載します。ABC 187 Eでは、後述の通り隣接した２点のみに対してクエリされますが、一般的な２頂点が与えられた時の考察をします。その上で、これらに包含されるこの問題を解きます。
オイラーツアー
木のオイラーツアーについては過去記事:オイラーツアーした木に対するクエリを参照してください。但し、以下、解説では、
- STEPを1-originで記載しています
- Discovery/Finishingをin/outと表現しています
以下のようにDFS順にパスを記録します。
図では20step(20step目は終了)のツアーを行いました。これと同時に、costを同じ長さで定義します。これは、この瞬間のvisitのノードのコストではなくて、計算が終わったときのこのノードのコストを示します。(これは圧縮することも可能です)
一般的なクエリと、オイラーツアー上での考え方
ABC-Eでは、ある辺の二頂点が与えられるため、以下のAかBのパターンかつ、隣接2頂点が与えられた場合のみを扱いますが、ここでは、任意の2頂点$a,b$が与えられたとします。
ポイントは、木ではある２点が与えられた時、「1.どちらかのノードがもう一方のLCAのノード」か「2.そうではないか」のどちらかでしかありません。言い換えると、「1.片方のノードが一方のノードの部分木上のノードである」か「2.そうではない」のどちらかです。次に、それぞれのパターンを記載します。両ノードが同一である場合は考慮しません。
適当な頂点1を根としてオイラーツアーをしたパスとクエリであり得るバリエーションを以下に示します。"例:"はa,bのパラメータです。
この問題の操作は$a$側のノードから木を塗りつぶし、$b$はその塗りつぶしを防ぐ。塗りつぶされたノードはコストが$+x$される。という操作に見えます。
まず、$B,C,D$の操作は$b$の部分木以外のすべてのノード塗りつぶす操作で簡単に見えます。
ところが、$A$の操作が少し難しそうに見えます。この操作は良く見ると、(Aは$a=3$の方が深いので)$b=1$の子($2と7$)の部分木の中で$a$を含む部分木(つまり2の部分木)のすべてを塗りつぶす動作となるようです。
これをオイラーツアーのパスと先ほど定義したcostすればよい区間を考えたのが図の下のテーブルです。青い両矢印直線はコストxを足せばいい区間です。"x"は$b$で止められている場所と考えると良いです。
$B,C,D$に関しては、非常にシンプルで、$b$の部分木以外のすべてのノードxを加算すればよいです。$b$の部分木は$b$のin, outの内部に含まれるノードなので、bの部分木でないとは$b$のinより小さいかoutより大きいすべてのcostにxを加算すればよいこととなります。
$A$の場合はアプローチが異なり、in, outだけでの加算範囲の判定が困難です。$a$が$b$の部分木であることは明らかのため、$a$のinより小さいSTEPで$b$は訪問されており、$a$のoutより大きなSTEPで$b$が訪問されることは明らかです。ただし、その左右に出現する$b$は１度とは限りません。例えば、図のpatAのように、3のoutの右側に1はSTEP 11と19の2度出現しています。これは、１の出現順順序を記録しておき、([1,11,19]のように)、$a$のinかout(必ずある区間に含まれるのでどちらでも良い)をキーに二分探索することで求まります。この2つのindexを+-1した区間にxを加算してやればよいです。
ABC 187-Eの場合
さて、それでは出題された問題を考えます。この問題では、2点$a,b$が与えられるのではなく、木の辺が与えられます。木でこの２点を考えると必ず一方はLCAノードです。また、隣接した２点であるため、この深さの差は必ず1となります。
※図上少し混乱しやすいですが、patEでもpatFでも深いノードが主体になるため、in/outを注目すればいいのは3側のみです。
この条件下では、上記のpatAとpatBを非常にシンプルに考えることができます。
- LCAは自明なのでの判定をする必要はない。尚、単にどちらかが部分木に含まれるかを確認するだけなら、一方のin/outがもう一方のin/outに包含されるかを確認すればよいだけなのでこれは面倒ではないです。
- inが若いノードがLCAノードである(オイラーツアーを考えると自明です)
- 深いノードの-+1のSTEPは必ず浅いノードを訪問している(patAの場合でも、加算すればよい区間の判定に訪問STEPの記録や二分探索などは不要でのin/out区間である)
つまり、以下のように考えます。あるノード$i$の深さを$dep(i)$とし、$add(l,r,x)$が$cost$の区間$[l,r)$にxを区間和する関数なら、ノード$a$のin,outを$ain,aout$で、ノード$b$のin,outを$bin,bout$するとき、
- $dep(a)$ > $dep(b)$の時、patEであり、$add(aout, ain+1, x)$すればよい(この場合は、$a$としてノード3のin/outが参照されます)
- $dep(a)$ < $dep(b)$の時、patFであり、$add(1, bin, x), $add(bout+1, 20, x)$ すればよい(つまり、$b$の部分木以外すべてにコスト追加/この場合は、$b$としてノード3のin/outが参照されます)
実装
Range Addする必要はありますが、QueryはSumのみであり、最後の１回だけ取ればよいため、imosで良いです。
また、eとqの数が多いので、pythonの場合、input = sys.stdin.readlineは必須です。実行時間が400msくらい変わります。
n = int(input())
dat = []
G = [[] for _ in range(n)]
for i in range(n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
dat.append([a, b])
G[a].append(b)
G[b].append(a)
q = []
rootnode = 0
depth = [-1] * n
nodein = [-1] * n
nodeout = [-1] * n
q.append([rootnode, 0, 0])
curtime = -1
parent = [None] * n
while len(q) != 0:
curtime += 1
curnode, curdepth, vcost = q.pop()
if curnode >= 0: # 行き掛け
if nodein[curnode] == -1:
nodein[curnode] = curtime
depth[curnode] = curdepth
isLeaf = True
if len(G[curnode]) == 0: # 子がいないときの処理
nodeout[curnode] = curtime + 1
for nextnode in G[curnode][::-1]:
if depth[nextnode] != -1:
continue
isLeaf = False
q.append([~curnode, curdepth, 0])
q.append([nextnode, curdepth + 1, 0])
parent[nextnode] = curnode
if isLeaf is True:
q.append([~curnode, curdepth, 0])
else: # もどりがけ
curnode = ~curnode
if nodein[curnode] == -1:
nodein[curnode] = curtime
nodeout[curnode] = curtime + 1
qq = int(input())
imos = [0] * (curtime + 10)
for qqq in range(qq):
t, e, x = map(int, input().split())
if t == 1:
a, b = dat[e - 1]
else:
b, a = dat[e - 1]
ain, aout = nodein[a], nodeout[a]
bin, bout = nodein[b], nodeout[b]
# a=スタートがbより深い場合
if ain > bin: # 部分木 PatEだけに加算
imos[ain] += x
imos[aout + 1] += -x
else:
imos[0] += x
imos[bin] += -x
imos[bout + 1] += x
imos[curtime + 2] += -x
cur = 0
buf = [0] * (curtime + 10)
for i in range(curtime + 5):
cur += imos[i]
buf[i] = cur
for i in range(n):
print(buf[nodein[i]])
C++
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <stack>
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
//////////////////////////////////////
#include <iostream>
using namespace std;
#define dp(arg) do { cout << #arg << ":"; dprint(arg); } while(0)
template <typename T> void dprint(T arg) { cout << arg << "\n"; }
template <typename T> void dprint(const vector<T>& arg) { for_each(begin(arg), end(arg), [](T value){ cout << value << " "; } ); cout << "\n"; }
template <typename T> void dprint(const vector<vector<T>>& arg) { for_each(begin(arg), end(arg), [=](vector<T> arg2){ dprint(arg2); cout << "\n";} ); }
//////////////////////////////////////
#define ll long long int
struct qdata{
int curNode = 0;
int curDepth = 0;
};
int main(int argc, char *argv[]) {
int n;
cin >> n;
vector<vector<int>> G(n);
vector<pair<int, int>> dat(n);
REP(i, n-1){
int a,b;
cin >> a >> b;
--a; --b;
dat[i] = make_pair(a, b);
G[a].push_back(b);
G[b].push_back(a);
}
int rootnode = 0;
vector<int> depth(n);
vector<int> nodeIn(n);
vector<int> nodeOut(n);
vector<int> parent(n);
REP(i, n){
depth[i] = -1;
nodeIn[i] = -1;
nodeOut[i] = -1;
parent[i] = -1;
}
qdata curDat;
qdata nextDat;
qdata nextDat2;
qdata nextDat3;
stack<qdata> q;
curDat.curDepth = 0;
curDat.curNode = rootnode;
q.push(curDat);
int curtime = -1;
bool isLeaf;
while(q.size() > 0){
++curtime;
curDat = q.top();
q.pop();
if(curDat.curNode >= 0) {
if (nodeIn[curDat.curNode] == -1) nodeIn[curDat.curNode] = curtime;
depth[curDat.curNode] = curDat.curDepth;
isLeaf = true;
for(auto nextNode: G[curDat.curNode]){
if(depth[nextNode] != -1) continue;
isLeaf = false;
nextDat.curNode = (-curDat.curNode-1);
nextDat.curDepth = curDat.curDepth;
q.push(nextDat);
nextDat2.curNode = (nextNode);
nextDat2.curDepth = curDat.curDepth + 1;
q.push(nextDat2);
}
if(isLeaf == true){
nextDat3.curNode = (-curDat.curNode-1);
nextDat3.curDepth = curDat.curDepth;
q.push(nextDat3);
}
} else {
curDat.curNode = -curDat.curNode - 1;
if(nodeIn[curDat.curNode] == -1) nodeIn[curDat.curNode] = curtime;
nodeOut[curDat.curNode] = curtime + 1;
}
}
int qq;
cin >> qq;
vector<ll> imos(curtime + 10);
REP(i, curtime + 10){
imos[i] = 0;
}
pair<ll, ll> edat;
ll t, e, x;
ll ain, aout, bin, bout;
REP(qqq, qq){
cin >> t >> e >> x;
edat = dat[e-1];
if(t == 1){
ain = nodeIn[edat.first];
aout = nodeOut[edat.first];
bin = nodeIn[edat.second];
bout = nodeOut[edat.second];
} else {
ain = nodeIn[edat.second];
aout = nodeOut[edat.second];
bin = nodeIn[edat.first];
bout = nodeOut[edat.first];
}
if(ain > bin) {
imos[ain] += x;
imos[aout + 1] += -x;
} else {
imos[0] += x;
imos[bin] += -x;
imos[bout + 1] += x;
imos[curtime + 2] += -x;
}
}
ll cur = 0;
vector<ll> buf(curtime + 10);
REP(i, curtime + 5){
cur += imos[i];
buf[i] = cur;
}
REP(i, n) {
//cout << nodeIn[i] << "\n";
}
REP(i, n){
cout << buf[nodeIn[i]] << "\n";
}
REP(i, n){
}
}