[PYTHON] AtCoder ABC 187 E --Through Path "Euler Tour + Interval Sum" approach and consideration of any two non-edge queries
https://atcoder.jp/contests/abc187/tasks/abc187_e The tree DP solution is appropriate, but it can also be solved by the interval sum calculation using the route followed by Euler Tour. I will describe this consideration process once it is recorded. In ABC 187 E, as described later, only two adjacent points are queried, but we will consider when two general vertices are given. Then, we will solve this problem contained in these.
Euler tour
For more information on Euler tours of trees, see Past article: Queries for Euler-toured trees. However, in the explanation below,
--STEP is described in 1-origin --Discovery/Finishing is expressed as in/out
Comb the path back in DFS order as shown below.
In the figure, we did a 20step tour (the 20th step is over). At the same time, define cost with the same length. This shows the cost of this node at the end of the calculation, not the cost of the visit node at this moment . (It can also be compressed)
General queries and ideas on Euler tours
In ABC-E, since two vertices of a certain edge are given, only the following A or B pattern and two adjacent vertices are given, but here, any two vertices $ a, b $ Is given.
The points are only "1. One node is the other LCA node" or "2. Isn't it?" Given two points in the tree. >. In other words, either "1. One node is a node on the subtree of one node" or "2. Not". Next, each pattern is described. It does not consider if both nodes are the same.
Below are variations that can be Euler-toured paths and queries rooted at the appropriate vertex 1. "Example:" is a parameter of a, b.
The operation in this problem fills the tree from the node on the $ a $ side, and $ b $ prevents that fill. Filled nodes cost $ + x $. It looks like the operation. First, $ B, C, D $ operations are easy to see with all node fill operations except the $ b $ subtree. However, the operation of $ A $ seems to be a little difficult. If you look closely at this operation, you can see that the subtree containing $ a $ (that is, 2) in the subtree of the children ($ 2 and 7 $) of $ b = 1 $ (because A is deeper in $ a = 3 $) It seems that it will be the operation to fill all of the subtree).
The table at the bottom of the figure considers this as the Euler tour pass and the section that should be costed as defined earlier. The blue double-headed straight line is the section where the cost x should be added. Think of the "x" as being stopped by $ b $.
For $ B, C, D $, it's very simple, just add all the nodes x except the subtree of $ b $. Since the subtree of $ b $ is a node contained inside the in and out of $ b $, if it is not a subtree of b, x should be added to all costs smaller than in or larger than out of $ b $. It will be. In the case of $ A $, the approach is different, and it is difficult to judge the addition range only by in and out. Since it is clear that $ a $ is a subtree of $ b $, $ b $ is visited in a STEP smaller than in of $ a $, and $ b $ is visited in a STEP larger than out of $ a $. It is clear that it will be done. However, $ b $ that appears on the left and right is not always once. For example, as shown in patA in the figure, 1 appears twice in STEP 11 and 19 on the right side of out of 3. This records the order of appearance of 1 (as in [1,11,19]) and divides it into two using $ a $ in or out (it does not matter because it is always included in a certain interval). It can be found by searching. You can add x to the interval of + -1 of these two indexes.
For ABC 187-D
Now, let's think about the question that was asked. In this problem, the edges of the tree are given instead of the two points $ a, b $. Considering these two points in a tree, one is always an LCA node. Also, since there are two adjacent points, the difference in depth is always 1.
- It is a little confusing on the figure, but since deep nodes are the main components in both patE and patF, you should pay attention to in/out only on the 3rd side.
Under this condition, the above patA and patB can be considered very simply.
- LCA is self-explanatory, so there is no need to make a judgment. If you just want to check if one of them is included in the subtree, you only have to check if one in/out is included in the other in/out, so this is not troublesome. --The node with the younger in is the LCA node (obvious considering the Euler tour) --The -+1 STEP of a deep node always visits a shallow node (even in the case of patA, it is an in/out section that does not require recording of the visit STEP or binary search to determine the section to be added. )
In other words, think as follows. If the depth of a node $ i $ is $ dep (i) $ and $ add (l, r, x) $ is a function that sums x to the interval $ [l, r) $ of $ cost $, the node When in and out of $ a $ are $ ain and aout $ and in and out of node $ b $ are $ bin and bout $
-When $ dep (a) $> $ dep (b) $, it is patE, and $ add (aout, ain + 1, x) $ should be used (in this case, in/of node 3 as $ a $. out is referenced) -When $ dep (a) $ <$ dep (b) $, it is patF, and $ add (1, bin, x), $ add (bout + 1, 20, x) $ should be used (that is, $ Add cost to everything except subtree of b $/In this case, node 3 in/out is referred to as $ b $)
Implementation
You need to Range Add, but imos is fine because Query is Sum only and you only have to take the last one.
Also, due to the large number of e and q, input = sys.stdin.readline is required for python. The execution time changes by about 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: #Going out
if nodein[curnode] == -1:
nodein[curnode] = curtime
depth[curnode] = curdepth
isLeaf = True
if len(G[curnode]) == 0: #Processing when there is no child
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: #Return
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=If the start is deeper than b
if ain > bin: #Add to partial tree PatE only
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]])
https://atcoder.jp/contests/abc187/submissions/19182075
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), [](Tvalue){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){
}
}