企业网站的需求是什么,旅游的网页设计模板,安卓开发是做什么的,婚庆一条龙价目表题目链接 对于每一个节点#xff0c;记录这个节点所在链的信息#xff1a; ls:#xff08;链的上端点#xff09;距离链内部近期的白点距离 rs:#xff08;链的下端点#xff09;距离链内部近期的白点距离 注意以上都是实边 虚边的信息用一个set维护。 set维护的是… 题目链接 对于每一个节点记录这个节点所在链的信息 ls:链的上端点距离链内部近期的白点距离 rs:链的下端点距离链内部近期的白点距离 注意以上都是实边 虚边的信息用一个set维护。 set维护的是对于每一个不是链上可是this的子树那些子树中距离this近期的白点距离。 #include stdio.h
#include string.h
#include set
#include algorithm
#include iostream
#include vector
template class T
inline bool rd(T ret) {char c; int sgn;if (c getchar(), c EOF) return 0;while (c ! - (c0 || c9)) c getchar();sgn (c -) ? -1 : 1; ret (c -) ? 0 : (c - 0); while (c getchar(), c 0c 9) ret ret * 10 (c - 0); ret * sgn; return 1; } template class T inline void pt(T x) { if (x 0) { putchar(-); x -x; } if (x9) pt(x / 10); putchar(x % 10 0); } using namespace std; typedef long long ll; const int inf 1e9; const int N 1e5 10; struct Node *null; struct Node{ multisetintchain; Node *fa, *ch[2]; int size; int col, ls, rs, id, len, edge; //黑色col-inf, 白色col0 len是链长 bool rev; inline void put(){ printf(%d son:%d,%d fa:%d len:%d (%d,%d) col:%d\n, id, ch[0]-id, ch[1]-id, fa-id, len, ls, rs, col); for (auto i : chain)printf(%d , i); puts(); } inline void clear(int _id){ fa ch[0] ch[1] null; size 1; rev 0; len edge 0; id _id; chain.clear(); chain.insert(inf); col inf; ls rs inf; } inline void push_up(){ size 1 ch[0]-size ch[1]-size; len edge ch[0]-len ch[1]-len; int m0 min(col, *chain.begin()), ml min(m0, ch[0]-rs edge), mr min(m0, ch[1]-ls); ls min(ch[0]-ls, ch[0]-len edge mr); rs min(ch[1]-rs, ch[1]-len ml); } inline void push_down(){ if (rev){ ch[0]-flip(); ch[1]-flip(); rev 0; } } inline void setc(Node *p, int d){ ch[d] p; p-fa this; } inline bool d(){ return fa-ch[1] this; } inline bool isroot(){ return fa null || fa-ch[0] ! this fa-ch[1] ! this; } inline void flip(){ if (this null)return; swap(ch[0], ch[1]); rev ^ 1; } inline void go(){//从链头開始更新到this if (!isroot())fa-go(); push_down(); } inline void rot(){ Node *f fa, *ff fa-fa; int c d(), cc fa-d(); f-setc(ch[!c], c); this-setc(f, !c); if (ff-ch[cc] f)ff-setc(this, cc); else this-fa ff; f-push_up(); } inline Node*splay(){ go(); while (!isroot()){ if (!fa-isroot()) d() fa-d() ? fa-rot() : rot(); rot(); } push_up(); return this; } void debug(Node *x){ if (x null)return; x-put(); debug(x-ch[0]); debug(x-ch[1]); } inline Node* access(){//access后this就是到根的一条splay而且this已经是这个splay的根了 for (Node *p this, *q null; p ! null; q p, p p-fa){ p-splay(); // debug(q); puts(); debug(p); puts(); if (p-ch[1] ! null) p-chain.insert(p-ch[1]-ls); if (q ! null) p-chain.erase(p-chain.find( q-ls )); p-setc(q, 1); p-push_up(); // debug(q); puts(); debug(p); puts(); } return splay(); } inline Node* find_root(){ Node *x; for (x access(); x-push_down(), x-ch[0] ! null; x x-ch[0]); return x; } void make_root(){ access()-flip(); } void cut(){//把这个点的子树脱离出去 access(); ch[0]-fa null; ch[0] null; push_up(); } void cut(Node *x){ if (this x || find_root() ! x-find_root())return; else { x-make_root(); cut(); } } void link(Node *x){ if (find_root() x-find_root())return; else { make_root(); fa x; } } }; Node pool[N], *tail; Node *node[N]; vectorintG[N]; void dfs(int u, int fa){ for (int v : G[u]){ if (v fa)continue; node[v]-fa node[u]; node[v]-edge 1; dfs(v, u); node[u]-chain.insert(node[v]-ls); } node[u]-push_up(); } int n, q; void debug(Node *x){ if (x null)return; x-put(); debug(x-ch[0]); debug(x-ch[1]); } int main(){ while (cin n){ tail pool; null tail; null-clear(0); null-size 0; for (int i 1; i n; i) { G[i].clear(); node[i] tail; node[i]-clear(i); } for (int i 1, u, v; i n; i){ rd(u); rd(v); G[u].push_back(v); G[v].push_back(u); } dfs(1, 1); // for (int i 1; i n; i)debug(node[i]), puts(); rd(q); while (q--){ int u, v; rd(u); rd(v); if (u 0) { node[v]-access(); if (node[v]-col inf)node[v]-col 0; else node[v]-col inf; node[v]-push_up(); } else { node[v]-access(); int ans min(*node[v]-chain.begin(), node[v]-rs); if (ans inf)ans -1; pt(ans); puts(); } // for (int i 1; i n; i)debug(node[i]), puts(); } } return 0; } 转载于:https://www.cnblogs.com/lxjshuju/p/7388973.html
