生病了，但是依然强悍。
好久没打 YACS 比赛了。
T1 树的路径
题目大意
https://www.iai.sh.cn/problem/867
给定一棵 \(n\) 个结点的树，点的编号为 \(1\) 到 \(n\)，\(1\) 号点为根。树上第 \(i\) 个点与其父亲的距离为 \(d_i\)。给定一个上限 m，与一个编号为 \(u\) 的点，定义 \(S(u,m)\) 为 \(u\) 的子树中，与 \(u\) 距离不超过 \(m\) 的点的数量。
对任意点 \(1≤i≤n\)，请计算并输出 \(S(i,m)\)。
\(1\le n\le 2\times 10^5, 1\le m\le 10^{18}, 1\le d_i\le 10^9\).
思路
记 \(dis_i\) 表示 \(i\) 到根节点的路径长度，则 \(u\) 子树内节点 \(v\) 到 \(u\) 的距离不超过 \(m\) 等价于 \(dis_v-dis_u\le m\)，即 \(dis_v\le dis_u+m\)，同时 \(v\in subtree(u)\)。
搞出 dfn 序列，然后在子树内这一限制变成了一段区间，将 \(dis,dis+m\) 离散化，变成二维偏序问题，可以离线下来用一个 BIT 搞。
时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, ll> PII;
const int maxn = 2e5 + 5;
namespace IO_ReadWrite {
#define re register
#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
char _buf[1<<21], *p1 = _buf, *p2 = _buf;
template <typename T>
inline void read(T &x){
x = 0; re T f=1; re char c = gg;
while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
x *= f;return;
}
inline void ReadChar(char &c){
c = gg;
while(!isalpha(c)) c = gg;
}
template <typename T>
inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar('0' + x % 10);
}
template <typename T>
inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
int n, tI[maxn], timer, tO[maxn], rev[maxn];
vector <PII> e[maxn];
ll m, dis[maxn], ds[maxn * 2], nD, dpa[maxn];
inline void dfs(int u, int fa) {
dis[u] = dis[fa] + dpa[u];
rev[tI[u] = ++ timer] = u;
for(auto now : e[u]) {
int v = now.first;
if(v == fa) continue;
dfs(v, u);
}
tO[u] = timer;
}
int bit[maxn * 2];
inline int lowbit(int x) {return x & (-x);}
inline void upd(int x, int v) {
for(; x <= nD; x += lowbit(x))
bit[x] += v;
}
inline int psq(int x) {
int res = 0;
for(; x; x -= lowbit(x)) res += bit[x];
return res;
}
struct querys {
int op, id, pos;
int val;
bool operator <(const querys &X)const {
return pos < X.pos;
}
} q[maxn * 2];
int nQ, ans[maxn];
vector <int> qry[maxn];
int main () {
read(n); read(m);
rep(i, 2, n) {
int x;
read(x); read(dpa[i]);
e[x].push_back({i, dpa[i]});
}
dfs(1, 0);
rep(i, 1, n) ds[++ nD] = dis[i], ds[++ nD] = dis[i] + m;
sort(ds + 1, ds + nD + 1);
nD = unique(ds + 1, ds + nD + 1) - (ds + 1);
rep(i, 1, n) {
int val = lower_bound(ds + 1, ds + nD + 1, (dis[i] + m)) - ds;
dis[i] = lower_bound(ds + 1, ds + nD + 1, dis[i]) - ds;
q[++ nQ] = {1, i, tO[i], val};
q[++ nQ] = {-1, i, tI[i] - 1, val};
}
sort(q + 1, q + nQ + 1);
rep(i, 1, nQ) qry[q[i].pos].push_back(i);
rep(i, 1, n) {
upd(dis[rev[i]], 1);
// writeln(dis[rev[i]]);
for(auto id : qry[i]) {
int op = q[id].op, u = q[id].id, val = q[id].val;
// writeln(val);
ans[u] += op * psq(val);
}
}
// rep(i, 1, n) writeln(tI[i]);
rep(i, 1, n) writeln(ans[i]);
return 0;
}
T2 点对乘积
题目大意
https://www.iai.sh.cn/problem/871
给定一棵 \(n\) 个点，且以 \(1\) 号点为根的有根树，树上编号为 \(i\) 的点的父节点为 \(p_i\) ，权值为 \(x_i\) 。同时给定一个正整数 \(m\)。
请你求出有多少对点对 \((u,v)\)，满足 \(u\) 是 \(v\) 的祖先，且 \(x_u×x_v≤m\)。
\(n\le 10^5, x_i,m\le 10^9\)。
思路
双倍经验。
枚举 \(u\)，然后变成 \(v\in subtree(u)\)，熟悉吗？此时 \(v\neq u\)，特判一下即可。
然后就变成 \(x_v\le \dfrac m {x_u}\)。事实上不需要浮点数，有 \(x_v\le \left\lfloor\dfrac m {x_u}\right\rfloor\)，原因是 \(x_v\) 是整数，故 \(x_v\) 是不大于 \(\dfrac m {x_u}\) 的整数，而根据定义，\(\left\lfloor\dfrac m {x_u}\right\rfloor\) 是不大于 \(\dfrac m {x_u}\) 的最大整数，因此成立。
然后又变成二维偏序了。时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, int> PII;
const int maxn = 1e5 + 5;
namespace IO_ReadWrite {
#define re register
#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
char _buf[1<<21], *p1 = _buf, *p2 = _buf;
template <typename T>
inline void read(T &x){
x = 0; re T f=1; re char c = gg;
while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
x *= f;return;
}
inline void ReadChar(char &c){
c = gg;
while(!isalpha(c)) c = gg;
}
template <typename T>
inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar('0' + x % 10);
}
template <typename T>
inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
int n;
ll x[maxn], xs[maxn * 2], nX, m;
int tI[maxn], tO[maxn], timer, rev[maxn];
vector <int> e[maxn];
inline void dfs(int u) {
rev[tI[u] = ++ timer] = u;
for(auto v : e[u]) dfs(v);
tO[u] = timer;
}
struct querys {
int op, u, pos, val;
} q[maxn * 2];
int nQ;
vector <int> qry[maxn];
ll sum, ans[maxn];
int bit[maxn * 2];
inline int lowbit(int x) {return x & (-x);}
inline void upd(int x, int v) {
for(; x <= nX; x += lowbit(x))
bit[x] += v;
}
inline int psq(int x) {
int res = 0;
for(; x; x -= lowbit(x)) res += bit[x];
return res;
}
int main () {
read(n); read(m);
rep(i, 2, n) {
int u; read(u);
e[u].push_back(i);
}
dfs(1);
rep(i, 1, n) read(x[i]);
rep(i, 1, n) sum -= (1ll * x[i] * x[i] <= m);
rep(i, 1, n) {
xs[++ nX] = x[i];
xs[++ nX] = m / x[i];
}
sort(xs + 1, xs + nX + 1);
nX = unique(xs + 1, xs + nX + 1) - (xs + 1);
rep(i, 1, n) {
int val = lower_bound(xs + 1, xs + nX + 1, (m / x[i])) - xs;
q[++ nQ] = {1, i, tO[i], val};
q[++ nQ] = {-1, i, tI[i] - 1, val};
x[i] = lower_bound(xs + 1, xs + nX + 1, x[i]) - xs;
}
rep(i, 1, nQ) qry[q[i].pos].push_back(i);
rep(i, 1, n) {
upd(x[rev[i]], 1);
for(auto id : qry[i]) {
int op = q[id].op, u = q[id].u, val = q[id].val;
ans[u] += op * 1ll * psq(val);
}
}
rep(i, 1, n) sum += ans[i];
writeln(sum);
return 0;
}
T3 构图
题目大意
https://www.iai.sh.cn/problem/870
小爱想用 \(n\) 个点，\(k\) 条边来构造一张简单无向联通图（即无重边、无自环），她希望构造出的图能够满足前 \(m\) 个点度数恰好为 \(2\)。
请你帮忙求出满足条件的简单无向联通图的个数，由于答案可能很大，输出答案对 \(10^9+7\) 取模的结果。
\(n,k\le 50,0\le m\le 2\)。
思路
最困难的一集。
首先一点，\(n\) 个点 \(k\) 条边的有标号无向连通图计数是好做的。这篇文章 还给出了一个使用 Stirling 反演进一步优化复杂度的做法。
然后就变成了讨论前 \(m\) 个点之间的连接情况。代码没写。