#include #include #include namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia #include #include #include namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } }; using Base = std::vector>; Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} Graph(int n, const std::vector>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i static Graph Input(Cin& cin, int n, bool undirected, int m, bool offset = 0){ Graph res(n, undirected, m); for(int i=0; i> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(ei); } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i induce(int num, const std::vector& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i indexV(n), newV(num); for(int i=0; i= 0) indexV[i] = newV[mapping[i]]++; std::vector res; res.reserve(num); for(int i=0; i= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray getEdgeIndexArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i::Construct(numVertices(), src); } CsrArray getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray getAdjacencyArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray::Construct(numVertices(), src); } CsrArray getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector m_e; bool m_isUndir; }; } // namespace nachia #include #include #include #include #include namespace nachia{ class StaticTopTree{ public: struct Node{ int p = -1; int l = -1; int r = -1; int boundaryS = -1; int boundaryT = -1; enum Type{ TyCompress, TyRake1, TyRake2, TyEdge } ty = TyEdge; }; StaticTopTree(Graph tree, int root = 0){ int n = tree.numVertices(); m_n = n; std::vector parent; std::vector parentEdge; assert(tree.numEdges() == n-1); assert(0 <= root && root < n); m_root = root; if(tree.numVertices() == 1){ m_n = 1; return; } nachia::CsrArray adj = tree.getAdjacencyArray(true); parent.assign(n, -2); parentEdge.assign(n, -1); std::vector bfs = {m_root}; bfs.reserve(n); parent[m_root] = -1; for(int i=0; i<(int)bfs.size(); i++){ int p = bfs[i]; for(int nx : adj[p]) if(parent[nx] == -2){ parent[nx] = p; bfs.push_back(nx); } } for(int i=0; i nd(n, 1); for(int i=n-1; i>=1; i--) nd[parent[bfs[i]]] += nd[bfs[i]]; for(int p=0; p troot(n, -1); int trp = n*2-3; troot[bfs[0]] = --trp; for(int s : bfs) if(parent[s] < 0 || adj[parent[s]][0] != s){ struct SzNode { int sz, vid, nx; }; std::vector sznode; std::vector Hid = {0}; std::vector boundarySize; if(parent[s] >= 0){ sznode.push_back({ 1, parentEdge[s], adj[parent[s]][0] }); Hid.push_back(Hid.back()+1); } for(int p=s; ; p=adj[p][0]){ if(adj[p].size() == 0) break; for(int e=1; e Que = { { troot[s], 0, (int)sznode.size() } }; Que.reserve(sznode.size() * 2); for(int i=0; i<(int)Que.size(); i++){ int tp = Que[i].p, l = Que[i].l, r = Que[i].r; if(r-l == 1){ troot[sznode[l].nx] = tp; continue; } int m = Que[i].l; while(boundarySize[m] - boundarySize[l] < boundarySize[r] - boundarySize[m+1]) m++; if(Hid[l] == Hid[m]) m_node[tp].ty = Node::TyRake2; else if(Hid[m] == Hid[r]) m_node[tp].ty = Node::TyRake1; else m_node[tp].ty = Node::TyCompress; int pl = (m-l == 1) ? sznode[l].vid : -1; if(pl == -1) pl = --trp; int pr = (r-m == 1) ? sznode[m].vid : -1; if(pr == -1) pr = --trp; m_node[tp].l = pl; m_node[tp].r = pr; m_node[pl].p = tp; m_node[pr].p = tp; Que.push_back({ pl, l, m }); Que.push_back({ pr, m, r }); } } for(int i=0; i m_node; std::vector m_handle; }; } // namespace nachia #include #include #include int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); using std::cin; using std::cout; int N; cin >> N; nachia::Graph tree(N, true); for(int i=0; i> u >> v; tree.addEdge(u, v); } std::vector A(N); for(int i=0; i> A[i]; A[i] *= 2; } if(N == 1){ int Q; cin >> Q; for(int i=0; i>> frac(st.numNodes()); std::vector> fracsum(st.numNodes()); using NodeTy = nachia::StaticTopTree::Node::Type; auto dfs = [&](auto& dfs, int p) -> std::vector { auto v = st.getNode(p); if(v.ty == v.TyEdge){ fracsum[p] = {0}; return {}; } int mid = -1; if(v.ty == NodeTy::TyCompress) mid = st.getNode(v.l).boundaryT; if(v.ty == NodeTy::TyRake1) mid = st.getNode(v.r).boundaryT; if(v.ty == NodeTy::TyRake2) mid = st.getNode(v.l).boundaryT; auto P = dfs(dfs, v.l); auto Q = dfs(dfs, v.r); int iP = 0, iQ = 0, iC = 0; int f = P.size() + Q.size() + 1; std::vector res(f); std::vector> fract(f+1); for(int ff=0; ff sum(f+1); for(int i=0; i sumA(N+1); for(int i=0; i addW(st.numNodes(), 0); std::vector weightBuf(N); auto QUERY = [&](int l, int r, int k, int delta) -> int { auto WeightOfVtx = [l,r,k,delta,&A](int p) -> long long { return ((l <= p && p < r) ? k + A[p] : 0) + ((delta == p) ? 1 : 0); }; int nl = lower_bound(qarr.begin(), qarr.end(), l) - qarr.begin(); int nr = lower_bound(qarr.begin(), qarr.end(), r) - qarr.begin(); int nid = st.numNodes() - 1; long long lwt = 0; long long rwt = 0; long long thres = (sumA[r] - sumA[l] + (long long)(r-l) * k + 1) / 2; while(st.getNode(nid).ty != NodeTy::TyEdge){ auto node = st.getNode(nid); auto nodel = st.getNode(node.l); auto noder = st.getNode(node.r); long long lwtt = 0, rwtt = 0; int xl = frac[nid][nl].first, yl = frac[nid][nl].second; int xr = frac[nid][nr].first, yr = frac[nid][nr].second; long long xw = fracsum[node.l][xr] - fracsum[node.l][xl] + (long long)(xr - xl) * k + addW[node.l]; long long yw = fracsum[node.r][yr] - fracsum[node.r][yl] + (long long)(yr - yl) * k + addW[node.r]; switch(node.ty){ case NodeTy::TyCompress : { lwtt = lwt + xw + WeightOfVtx(nodel.boundaryS); rwtt = rwt + yw + WeightOfVtx(noder.boundaryT); if(thres < lwtt){ nl = xl; nr = xr; nid = node.l; rwt = rwtt; } else if(thres < rwtt){ nl = yl; nr = yr; nid = node.r; lwt = lwtt; } else return nodel.boundaryT; } break; case NodeTy::TyRake1 : { lwtt = lwt + xw + WeightOfVtx(nodel.boundaryS); rwtt = rwt + yw + WeightOfVtx(noder.boundaryT); if(thres < lwtt){ nl = xl; nr = xr; nid = node.l; rwt = rwtt; } else if(thres < rwtt){ nl = yl; nr = yr; nid = node.r; lwt = lwtt + rwt; rwt = 0; } else return nodel.boundaryT; } break; case NodeTy::TyRake2 : { lwtt = lwt + xw + WeightOfVtx(nodel.boundaryT); rwtt = rwt + yw + WeightOfVtx(noder.boundaryT); if(thres < lwtt){ nl = xl; nr = xr; nid = node.l; lwt = rwtt + lwt; rwt = 0; } else if(thres < rwtt){ nl = yl; nr = yr; nid = node.r; lwt = lwtt; } else return nodel.boundaryS; } break; default: break; } } auto fnode = st.getNode(nid); lwt += WeightOfVtx(fnode.boundaryS); rwt += WeightOfVtx(fnode.boundaryT); return lwt > rwt ? fnode.boundaryS : fnode.boundaryT; }; int Q; cin >> Q; long long sumX = 0; for(int q=0; q> ap >> bp >> kp >> delta; long long a = (ap + sumX % N) % N; long long b = (bp + sumX % N * 2) % N; long long k = (kp + sumX % 150001 * sumX % 150001) % 150001; int l = std::min(a, b); int r = std::max(a, b) + 1; for(int p=st.handleOfVtx(delta); p>=0; p=st.getNode(p).p) addW[p]++; int x = QUERY(l, r, k*2, delta); for(int p=st.handleOfVtx(delta); p>=0; p=st.getNode(p).p) addW[p]--; sumX += x; cout << x << '\n'; } return 0; }