前言
一开始以为是一坨数据结构, 结果是一坨杂题。
BZOJ 3306
题目大意: 给一棵带点权树, 要求支持:
1.单点点权修改。
2.子树点权最大值。
3.换根。
解题报告
据说正解是dfn序加上一些乱搞…但是lct明显是可以做的。
在lct上用multiset打标记表示子树最大值, 复杂度多个log但是好写啊。
自己zz..prepare()里面写反updata和insert, 然后没能把自己的子树最大值更新上去…RE不断*1h+
代码
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <climits> #include <set> using namespace std; typedef long long LL; const int MAXN = 100010; namespace LCT { const int MAXD = MAXN; struct Node { int ch[2], fa; bool tfa, rev; int val, mx; multiset<int> vir; } d[MAXD]; inline void initialize () { d[0].mx = INT_MIN; d[0].vir.insert(INT_MIN); } inline void updata (int u) { d[u].mx = max( max(d[u].val, *d[u].vir.rbegin()), max(d[d[u].ch[0]].mx, d[d[u].ch[1]].mx)); } void makeNode (int u, int f, int v) { d[u].fa = f, d[u].mx = d[u].val = v; d[u].vir.insert(INT_MIN); } inline void prepare (int u) { updata(u); d[d[u].fa].vir.insert(d[u].mx); } inline void rotate (int x) { int y = d[x].fa; bool f = d[y].ch[1] == x; d[y].ch[f] = d[x].ch[!f]; d[d[y].ch[f]].fa = y; d[x].ch[!f] = y; d[x].fa = d[y].fa; d[y].fa = x; swap(d[x].tfa, d[y].tfa); if(d[x].tfa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x; updata(y), updata(x); } inline void filp (int u) { d[u].rev ^= 1, swap(d[u].ch[0], d[u].ch[1]); } inline void pushdown (int u) { if(d[u].rev) { filp(d[u].ch[0]), filp(d[u].ch[1]); d[u].rev = false; } } void downlazy (int u) { if(d[u].fa && d[u].tfa) downlazy(d[u].fa); pushdown(u); } inline void splay (int x) { downlazy(x); while(d[x].tfa) { int y = d[x].fa, z = d[y].fa; if(d[y].tfa) { if((d[z].ch[1] == y) == (d[y].ch[1] == x)) rotate(y); else rotate(x); } rotate(x); } updata(x); } inline void access (int u) { int t = u, r = 0, tmp; while(u) { splay(u); if(d[u].ch[1]) d[u].vir.insert(d[d[u].ch[1]].mx); if(r) d[u].vir.erase(d[u].vir.find(d[r].mx)); d[d[u].ch[1]].tfa = false; d[d[u].ch[1] = r].tfa = true; updata(u); r = u; u = d[u].fa; } splay(t); } inline void makeroot (int u) { access(u), filp(u); } inline int maxValue (int u) { access(u); return max(*d[u].vir.rbegin(), d[u].val); } inline void modify (int u, int v) { access(u), d[u].val = v, updata(u); } } inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0'; return flg ? -ret : ret; } char buf[20]; int main () { int N = getInt(), Q = getInt(); LCT::initialize(); for(int i = 1; i<=N; i++) { int f = getInt(), v = getInt(); LCT::makeNode(i, f, -v); } for(int i = N; i>=2; i--) LCT::prepare(i); LCT::updata(1); while(Q --) { scanf("%s", buf); int x = getInt(); if(buf[0] == 'V') LCT::modify(x, -getInt()); else if(buf[0] == 'E') LCT::makeroot(x); else printf("%d\n", -LCT::maxValue(x)); } }
BZOJ 3991
题目大意: 给你一颗树, 每次把一个点的选取状态取反, 对每次操作输出操作后所有被选取点组成的子树边权和乘二。
解题报告
什么lct!虚树!
每次把dfn前驱和后继拉出来做lca算delta即可。
注意这题dfn成环, 自己脑残了总是写不过…
代码
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <climits> #include <set> using namespace std; typedef long long LL; const int MAXN = 100010; inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0'; return flg ? -ret : ret; } struct Node { int v, w, nxt; } d[MAXN*2]; int head[MAXN], etot; inline void addEdge (int a, int b, int c) { etot ++; d[etot].v = b; d[etot].w = c; d[etot].nxt = head[a]; head[a] = etot; } int dfn[MAXN], rev[MAXN], lst[MAXN], dfntot; int sz[MAXN], top[MAXN], fa[MAXN], depu[MAXN]; LL dep[MAXN]; int dfsSize (int u, int f) { rev[dfn[u] = ++dfntot] = u; sz[u] = 1; depu[u] = depu[f]+1; for(int e = head[u]; e; e = d[e].nxt) if(d[e].v != f) { dep[d[e].v] = dep[u]+d[e].w; sz[u] += dfsSize(d[e].v, u); } lst[u] = dfntot; return sz[u]; } void dfs (int u, int f) { fa[u] = f; if(!top[u]) top[u] = u; int mxp = 0; for(int e = head[u]; e; e = d[e].nxt) if(d[e].v != f && sz[d[e].v] > sz[mxp]) mxp = d[e].v; if(!mxp) return ; top[mxp] = top[u], dfs(mxp, u); for(int e = head[u]; e; e = d[e].nxt) if(d[e].v != f && d[e].v != mxp) dfs(d[e].v, u); } inline int getLCA (int a, int b) { //printf("calt:%d, %d\n", a, b); while(top[a] != top[b]) { if(depu[top[a]] < depu[top[b]]) b = fa[top[b]]; else a = fa[top[a]]; } return depu[a] < depu[b] ? a : b; } inline LL getDist (int a, int b) { int lca = getLCA(a, b); return dep[a]+dep[b]-dep[lca]*2LL; } LL ans = 0; set<int> st; int main () { int N = getInt(), M = getInt(); for(int i = 1; i<N; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); addEdge(a, b, c), addEdge(b, a, c); } dfsSize(1, 0); dfs(1, 0); while(M --) { int u = getInt(); set<int>::iterator it1, it2; int x1 = 0, x2 = 0; it1 = st.lower_bound(dfn[u]); if(st.size() == 0) { st.insert(dfn[u]); puts("0"); continue ; } if(it1 == st.end() || *it1 != dfn[u]) { // not exist if(it1 != st.end()) x2 = rev[*it1]; else x2 = rev[*st.begin()]; if(it1 != st.begin()) { --it1; x1 = rev[*it1]; } else it2 = st.end(), x1 = rev[*(--it2)]; st.insert(dfn[u]); if(x1 != 0 && x2 != 0) ans += getDist(x1, u)+getDist(u, x2)-getDist(x1, x2); else if(x1+x2 != 0 && (x1 == 0 || x2 == 0)) ans += 2*getDist(x1+x2, u); } else { it2 = it1, it2++; st.erase(it1); if(it2 != st.end()) x2 = rev[*it2]; else x2 = rev[*st.begin()]; if(it2 != st.begin()) { --it2; x1 = rev[*it2]; } else it2 = st.end(), x1 = rev[*(--it2)]; if(x1 != 0 && x2 != 0) ans -= getDist(x1, u)+getDist(u, x2)-getDist(x1, x2); else if(x1+x2 != 0 && (x1 == 0 || x2 == 0)) ans -= 2*getDist(x1+x2, u); } printf("%lld\n", ans); } }
BZOJ 2947
题目大意: 算了这题太水就不写了…
←懒人…
BZOJ 3544
题目大意: 给你一个数列, 询问数列区间和在模M意义下的最大值。
解题报告
又不是LCT
很水的…直接在set里挨个插入前缀和, 然后查询时差分, 按照贪心思想upper_bound一个相减即可。
代码
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <climits> #include <iostream> #include <set> using namespace std; typedef long long LL; inline LL getInt () { LL ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0'; return flg ? -ret : ret; } set<LL> st; int main () { int N = getInt(); LL M = getInt(); LL sum = 0, ans = 0; st.insert(0); for(int i = 1; i<=N; i++) { sum = (sum+getInt()%M+M)%M; set<LL>::iterator it = st.upper_bound(sum); if(it == st.end()) it = st.begin(); ans = max(ans, (sum-*it+M)%M); //printf("cur:%I64d, find:%I64d\n", sum, *it); st.insert(sum); } cout << ans << '\n'; }
BZOJ 2300
题目大意: 在线动态上凸包。
解题报告
就是个版…
自己计算几何太弱了..判凸包写错…叉乘写错…调了30min+
代码
#include <cstdio> #include <climits> #include <cstdlib> #include <cstring> #include <algorithm> #include <map> #include <cmath> #include <set> using namespace std; const int MAXN = 100010; const int MAXQ = 200020; struct Vector { int x, y; Vector () {} Vector (double a, double b):x(a), y(b) {} inline Vector operator + (const Vector & b) const {return Vector(x+b.x, y+b.y);} inline Vector operator - (const Vector & b) const {return Vector(x-b.x, y-b.y);} }; inline int cross (const Vector & a, const Vector & b) { return a.x*b.y-a.y*b.x; } inline double getDist (const Vector & a, const Vector & b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0'); return ret; } inline bool operator < (const Vector & a, const Vector & b) { if(a.x == b.x) return a.y<b.y; return a.x<b.x; } namespace DynamicHull { multiset<Vector> st; double cur_perimeter; void initialize (Vector a, Vector b, Vector c) { // 逆时针 st.clear(); st.insert(a), st.insert(b), st.insert(c); cur_perimeter = getDist(a, b)+getDist(b, c); } void insert (Vector vec) { multiset<Vector>::iterator it1 = st.lower_bound(vec), it2 = it1, tmp; it1--; if(cross(*it2-*it1, vec-*it1) <= 0) return ; cur_perimeter -= getDist(*it1, *it2); while(it1 != st.begin()) { tmp = it1, tmp--; if(cross(vec-*tmp, vec-*it1) >= 0) { cur_perimeter -= getDist(*tmp, *it1), st.erase(it1); it1 = tmp; } else break; } while(it2 != st.end()) { tmp = it2, tmp++; if(tmp == st.end()) break; if(cross(*tmp-vec, *it2-vec) <= 0) {//(3, -2)(2, 0) //printf("(%.2lf, %.2lf), (%.2lf, %.2lf)\n", it2->x, it2->y, tmp->x, tmp->y); cur_perimeter -= getDist(*tmp, *it2), st.erase(it2); it2 = tmp; } else break; } cur_perimeter += getDist(*it1, vec)+getDist(vec, *it2); st.insert(vec); } inline double perimeter () {return cur_perimeter;} } double ans[MAXQ]; Vector pos[MAXN]; int comd[MAXQ], arg[MAXQ]; bool vis[MAXN]; int main () { int N = getInt(), X = getInt(), Y = getInt(); int M = getInt(); for(int i = 1; i<=M; i++) pos[i].x = getInt(), pos[i].y = getInt(); int Q = getInt(); for(int i = 1; i<=Q; i++) { comd[i] = getInt(); if(comd[i] == 1) vis[arg[i] = getInt()] = true; } DynamicHull::initialize(Vector(0, 0), Vector(X, Y), Vector(N, 0)); for(int i = 1; i<=M; i++) if(!vis[i]) DynamicHull::insert(pos[i]); for(int i = Q; i; i--) { if(comd[i] == 1 && vis[arg[i]]) vis[arg[i]] = false, DynamicHull::insert(pos[arg[i]]); else ans[i] = DynamicHull::perimeter(); } for(int i = 1; i<=Q; i++) if(comd[i] == 2) printf("%.2lf\n", ans[i]); }
BZOJ 4260
题目大意: 盗图!
解题报告
最大区间异或和模板, 注意Trie清0时一定要清根节点…浪费时间+wa*3
代码
#include <cstdio> #include <climits> #include <cstdlib> #include <cstring> #include <algorithm> #include <map> #include <cmath> #include <set> using namespace std; const int MAXN = 400040; namespace Trie { const int MAXD = 400040*31; struct Node { int ch[2]; } d[MAXD]; int dtot; void clear() { dtot = 0; memset(d, 0, sizeof d[0]); } inline int newNode () {memset(d+(++dtot), 0, sizeof d[0]); return dtot;} inline void insert (int num) { int u = 0, bit = 29; while(bit>=0) { bool flg = (bool)(num&(1<<bit)); if(!d[u].ch[flg]) d[u].ch[flg] = newNode(); u = d[u].ch[flg]; -- bit; } } inline int query (int num) { int u = 0, bit = 29, ret = 0; while(bit>=0) { bool flg = !(bool)(num&(1<<bit)); if(!d[u].ch[flg]) u = d[u].ch[flg = !flg]; else u = d[u].ch[flg]; ret |= ((int)flg)<<bit; -- bit; } return ret; } } inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0'); return flg ? -ret : ret; } int A[MAXN], mxv[MAXN]; int main () { int N = getInt(); for(int i = 1; i<=N; i++) A[i] = getInt(); int cur = 0; Trie::insert(0); for(int i = 1; i<=N; i++) { cur ^= A[i]; Trie::insert(cur); mxv[i] = max(mxv[i-1], Trie::query(cur)^cur); } Trie::clear(), cur = 0; Trie::insert(0); int ans = 0; for(int i = N; i>=2; i--){ cur ^= A[i]; Trie::insert(cur); ans = max(ans, (Trie::query(cur)^cur)+mxv[i-1]); } printf("%d\n", ans); }
BZOJ 1492
CDQ写炸了…但是暂时不想补…留个坑…
BZOJ 4026
题目大意: 给你一个数组, 每次询问一个下标在区间[l, r]内元素乘积的欧拉函数, 对1e6+777取模。
解题报告
一开始想错, 然后各种zz错, 和这道题玩了好久…题目还是比较不错的
把欧拉函数展开之后可以转化为二维矩阵乘积问题, 由于没有修改用主席树维护。
我的主席树为什么比别人慢那么多…
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cstdlib> #include <vector> using namespace std; typedef long long LL; const int MOD = 1000777; const int MAXN = 50050; vector<int> fac[MOD]; bool isnprime[MOD]; int prec[MOD/3], ptot; int inv[MOD]; void preProcess (int lim) { for(int i = 2; i<lim; i++) { if(!isnprime[i]) {prec[++ptot] = i; fac[i].push_back(i);} for(int j = 1; j<=ptot&&prec[j]*i < lim; j++) { fac[prec[j]*i] = fac[i]; fac[prec[j]*i].push_back(prec[j]); isnprime[prec[j]*i] = true; if(i%prec[j] == 0) break; } } inv[1] = 1; for(int i = 2; i<MOD; i++) inv[i] = (MOD-(LL)(MOD/i)*inv[MOD%i]%MOD)%MOD; fac[1].push_back(1); } inline int inverse (int a) {return inv[a%MOD];} int N, Q; namespace PST { const int MAXD = 6800000; int val[MAXD], lc[MAXD], rc[MAXD], dtot; int roots[MAXN], tot = 1; void initialize () {val[0] = 1;} void solidfy(int & u, int r) { if(!u) u = r; else { solidfy(lc[u], lc[r]); solidfy(rc[u], rc[r]); } } inline void solidfyFloor () {solidfy(roots[tot], roots[tot-1]); ++tot;} int pos, ins; void insertF (int & u, int lb, int rb, int r) { if(lb > pos || rb < pos) return ; if(!u) u = ++dtot, val[u] = val[r]; val[u] = (LL)val[u]*ins%MOD; if(lb == rb) return ; int mid = (lb+rb)>>1; insertF(lc[u], lb, mid, lc[r]); insertF(rc[u], mid+1, rb, rc[r]); } void insert (int p, int v) { pos = p, ins = v; //printf("ins:p:%d, v:%d\n", p, v); insertF(roots[tot], 1, N, roots[tot-1]); } int ql, qr; int queryF (int & u, int lb, int rb) { if(!u || lb > qr || rb < ql) return 1; if(lb >= ql && rb <= qr) return val[u]; int mid = (lb+rb)>>1; return (LL)queryF(lc[u], lb, mid)*queryF(rc[u], mid+1, rb)%MOD; } int query (int L, int R) { ql = L, qr = R; int x = queryF(roots[R], 1, N); return (LL)x*inverse(queryF(roots[L-1], 1, N))%MOD; } } inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0'); return flg ? -ret : ret; } int A[MAXN], lst[MOD]; int main () { N = getInt(), Q = getInt(); int mxv = 0; PST :: initialize(); for(int i = 1; i<=N; i++) A[i] = getInt(), mxv = max(mxv, A[i]); preProcess(mxv+1); for(int i = 1; i<=N; i++) { //printf("cur:%d\n", A[i]); for(int j = 0; j<(int)fac[A[i]].size(); j++) { int x = fac[A[i]][j]; if(lst[x]) PST::insert(lst[x], (LL)inverse(x-1)*x%MOD); if(x != 1) PST::insert(lst[x]=i, x-1); } PST::solidfyFloor(); } int lastans = 0; for(int i = 1; i<=Q; i++) { int L = getInt()^lastans, R = getInt()^lastans; printf("%d\n", lastans=PST::query(L, R)); } } /* 10 10 1 87 267 1 3287 268 29 165 87 11 2 8 */
月考
月考了一波, 怀疑人生。
cqbz按照排名来分考试, 分数越高, 考试座位号越靠前, 考室号称之为’段位’。
好不容易上了王者, 停课掉到钻石, 化学64pts, 这次怕不止是要掉段, 还得坠楼了…
BZOJ 3658
题目大意: 二维平面上有N个最多K种颜色的点, 问选取一根平行于x轴的线段, 这根线段覆盖的点定义为线段上方(或下方)的所有点。
称一种覆盖是合法的当这种覆盖的所有点不包含全部K种颜色最多覆盖点数。
解题报告
好像做过?重新想, 扫描线+stl乱搞。
首先把每种颜色开一个set维护扫描线状态, 然后离散化一维用树状数组维护区间和扫描线做两遍即可。
具体看代码。
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cstdlib> #include <vector> #include <set> #include <stack> using namespace std; typedef long long LL; const int MAXN = 100010; inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0'); return flg ? -ret : ret; } struct CoordPoint { int x, y, c; } pos[MAXN], tmp[MAXN]; inline bool comp (const CoordPoint & a, const CoordPoint & b) { if(a.x == b.x) return a.y < b.y; return a.x < b.x; } inline bool compY (const CoordPoint & a, const CoordPoint & b) { if(a.y == b.y) return a.x < b.x; return a.y < b.y; } int N, K; int C[MAXN]; inline int lowbit (int a) {return a&-a;} inline void add (int p) { while(p <= N) ++C[p], p += lowbit(p); } inline int query (int p) { int ret = 0; while(p) ret += C[p], p -= lowbit(p); return ret; } int ans; set<int> st[MAXN]; stack<pair<int, int> > stk; int itot; void solve () { for(int i = 1; i<=K; i++) { st[i].clear(); st[i].insert(0); st[i].insert(itot+1); } memset(C, 0, sizeof C); std :: sort(tmp+1, tmp+N+1, compY); for(int i = 1, p; i<=N; i=p) { p = i; while(tmp[i].y == tmp[p].y && p <= N) { add(tmp[p].x); if(st[tmp[p].c].find(tmp[p].x) != st[tmp[p].c].end()) {++p; continue ;} stk.push(make_pair(tmp[p].c, tmp[p].x)); st[tmp[p].c].insert(tmp[p].x), ++p; } while(!stk.empty()) { int x = stk.top().second, c = stk.top().first, lb, rb; stk.pop(); set<int>::iterator it = st[c].find(x); --it; lb = *it; ++it, ++it, rb = *it; ans = max(ans, query(rb-1)-query(lb)-1); } } for(int c = 1; c<=K; c++) { set<int>::iterator it1 = st[c].begin(), it2 = it1; for(++it1; it1 != st[c].end(); it2=it1, it1++) ans = max(ans, query(*it1-1)-query(*it2)); } } bool vis[MAXN]; int main () { int T = getInt(); while(T --) { N = getInt(), K = getInt(); memset(vis, 0, sizeof vis); for(int i = 1; i<=N; i++) pos[i].x = getInt(), pos[i].y = getInt(), vis[pos[i].c = getInt()] = true; bool flg = false; for(int i = 1; i<=K; i++) if(!vis[i]) {flg = true; break;} if(flg) { printf("%d\n", N); continue ; } std :: sort(pos+1, pos+N+1, comp); itot = 1; memcpy(tmp, pos, sizeof pos); tmp[1].x = itot; for(int i = 2; i<=N; i++) if(pos[i].x != pos[i-1].x) tmp[i].x = ++itot; else tmp[i].x = itot; ans = 0; solve(); for(int i = 1; i<=N; i++) tmp[i].y = -tmp[i].y; solve(); printf("%d\n", ans); } }
BZOJ 3772
题目大意:给你一个树和M条路径, 问任意选择两条不相同路径恰好一条路径包含另一条的概率。
解题报告
如果路径是树上全部路径怎么做呢…
把路径用dfn转化为矩形然后上主席树维护, 注意包含和dfn序之间的转换不要太想当然了, 主席树手残在cpNode的时候顺便复制了lc和rc导致不断WA样例我太弱了…
卡内存, PST开50倍MLE了, 开45倍AC。
代码
#include <cstdio> #include <cstring> #include <climits> #include <algorithm> #include <cstdlib> #include <cmath> using namespace std; typedef long long LL; const int MAXN = 100010; inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0'); return flg ? -ret : ret; } int N, M; struct Node { int v, nxt; } d[MAXN*2]; int head[MAXN], etot; inline void addEdge (int a, int b) { etot ++; d[etot].v = b; d[etot].nxt = head[a]; head[a] = etot; } namespace PST { const int MAXD = MAXN*45; int sum[MAXD], lc[MAXD], rc[MAXD]; int dtot, roots[MAXN], tot = 1; int insp; void cNodeTo (int a, int b) {sum[b] = sum[a];} void insert (int & u, int lb, int rb, int r) { if(lb > insp || rb < insp) return ; if(!u) u = ++dtot, cNodeTo(r, u); //printf("at:%d, insp:%d, bd:(%d, %d)\n", u, insp, lb, rb); sum[u]++; if(lb == rb) return ; int mid = (lb+rb)>>1; insert(lc[u], lb, mid, lc[r]); insert(rc[u], mid+1, rb, rc[r]); } int ql, qr; int query (int u, int lb, int rb) { if(!u || lb > qr || rb < ql) return 0; if(ql <= lb && rb <= qr) return sum[u]; int mid = (lb+rb)>>1; return query(lc[u], lb, mid) + query(rc[u], mid+1, rb); } void solidfy (int & u, int r) { if(!u) u = r; else { solidfy(lc[u], lc[r]); solidfy(rc[u], rc[r]); } } inline int & root () {return roots[tot];} inline int & lroot () {return roots[tot-1];} inline void solidfyFloor () { solidfy(root(), lroot()); ++ tot; } inline int queryRect (int a, int b, int c, int d) { if(b >= c) swap(a, c), swap(b, d); ql = c, qr = d; int re = query(roots[b], 1, N)-query(roots[a-1], 1, N); return re; } } int dfn[MAXN], lst[MAXN], rev[MAXN], dfntot; int sz[MAXN], fa[MAXN], top[MAXN], dep[MAXN]; int dfs (int u, int f) { fa[u] = f, dep[u] = dep[f]+1; sz[u] = 1; for(int e = head[u]; e; e = d[e].nxt) if(d[e].v != f) sz[u] += dfs(d[e].v, u); return sz[u]; } void dfsHv (int u, int f) { if(!top[u]) top[u] = u; rev[dfn[u] = ++dfntot] = u; int mxp = 0; for(int e = head[u]; e; e = d[e].nxt) if(d[e].v != f && sz[d[e].v] > sz[mxp]) mxp = d[e].v; if(!mxp) {lst[u] = dfntot; return ;} top[mxp] = top[u], dfsHv(mxp, u); for(int e = head[u]; e; e = d[e].nxt) if(d[e].v != f && d[e].v != mxp) dfsHv(d[e].v, u); lst[u] = dfntot; } int getLCA (int a, int b) { while(top[a] != top[b]) { if(dep[top[a]] < dep[top[b]]) b = fa[top[b]]; else a = fa[top[a]]; } return dep[a]<dep[b] ? a : b; } int jump (int a, int step) { while(step > dep[a]-dep[top[a]]) step -= dep[a]-dep[top[a]]+1, a = fa[top[a]]; return rev[dfn[a]-step]; } struct Path { int a, b; } prec[MAXN]; inline bool operator < (const Path & a, const Path & b) { return dfn[a.a] < dfn[b.a]; } inline LL gcd (LL a, LL b) {return !b ? a : gcd(b, a%b);} int main () { N = getInt(), M = getInt(); for(int i = 1; i<N; i++) { int a = getInt(), b = getInt(); addEdge(a, b), addEdge(b, a); } for(int i = 1; i<=M; i++) prec[i].a = getInt(), prec[i].b = getInt(); dfs(1, 0); dfsHv(1, 0); for(int i = 1; i<=M; i++) if(dfn[prec[i].a] > dfn[prec[i].b]) swap(prec[i].a, prec[i].b); std :: sort(prec+1, prec+M+1); int cur = 1; for(int i = 1; i<=N; i++) { while(cur <= M && dfn[prec[cur].a] == i) { PST::insp = dfn[prec[cur].b]; PST::insert(PST::root(), 1, N, PST::lroot()); cur++; } PST::solidfyFloor(); } LL denominator = (LL)M*(M-1)/2, numerator = 0; for(int i = 1; i<=M; i++) { int a = prec[i].a, b = prec[i].b; int lca = getLCA(a, b); if(lca == a || lca == b) { if(lca == b) swap(a, b); int x = jump(b, dep[b]-dep[a]-1); numerator += PST::queryRect(1, dfn[x]-1, dfn[b], lst[b])-1; // 这个得函数内保证b<c numerator += PST::queryRect(lst[x]+1, N, dfn[b], lst[b]); } else numerator += PST::queryRect(dfn[a], lst[a], dfn[b], lst[b])-1; } LL g = gcd(numerator, denominator); numerator /= g, denominator /= g; printf("%lld/%lld\n", numerator, denominator); }
Join the discussion