T1 lcd
Statement:
给定 \(n (1 \le n \le 10^8)\)，问有多少对 \((i, j) (1 \le i, j \le n)\) 满足 \(\frac{xy}{\gcd(x, y)^2} \le 3\)。
Solution:
简单题。令 \(x' = \frac{x}{\gcd(x, y)}, y' = \frac{y}{\gcd(x, y)}\)，枚举 \((x', y')\) 并计算即可。
T2 cut
Statement:
给定一颗有 \(n(1 \le n \le 5 \times 10^5)\) 个节点的树，其中有 \(n - 1\) 条边，其中第 \(i\) 条边连接 \((u_i, v_i)\)。问断掉第 \(i\) 条边后，\(u_i, v_i\) 所处非空连通子图个数分别为多少。答案对 \(998244353\) 取模。
Solution:
比较简单的换根 \(\rm DP\)。
先考虑如何求出整棵树的非空连通子图个数，\(\rm DP\) 容易解决。设 \(f_{u, 0 / 1}\) 是不选/选 \(u\) 时，以 \(u\) 为根子树的非空连通子图个数。显然 \(f_{u, 0} = \sum_{v \in subtree(u)} {f_{v, 0} + f_{v, 1}}\)，\(f_{v, 1} = \prod_{v \in subtree(u)}{1 + f_{v, 1}}\)。
考虑切掉 \((u, v)\) 这条边后的影响，其中 \(u\) 是 \(v\) 的父亲，显然 \(v\) 中的答案是 \(f_{v， 1} + f_{v, 0}\)。现在计算 \(u\) 所处连通块的答案。显然我们需要割掉 \(v\) 对 \(u\) 带来的贡献，并加入 \(u\) 父亲割掉 \(u\) 后的贡献。于是考虑换根：设 \(g_{u, 0 / 1}\) 是不选/选 \(u\) 时，以 \(u\) 为根子树的非空连通子图个数。转移容易，但是有可能存在一个 \(f_{u, 0} + 1\) 为 \(mod\) 的倍数，不能使用逆元剔除贡献而是只能维护前缀和后缀积并将它们乘起来。
qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
struct edge{
int v, id, next;
}edges[N << 1];
int head[N], idx;
int f[N][2], g[N][2];
struct Edge{
int u, v, ansu, ansv;
}ans[N];
vector<int> pre[N], suf[N];
int qpow(int x, int y){
int ret = 1; x %= mod;
while(y){
if(y & 1) ret = ret * x % mod;
x = x * x % mod; y >>= 1;
}
return ret;
}
void add_edge(int u, int v, int id){
edges[++idx] = {v, id, head[u]};
head[u] = idx;
}
int n;
void dfs1(int u, int fa){
f[u][1] = 1;
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(v == fa) continue;
dfs1(v, u); f[u][0] = (f[u][0] + ((f[v][1] + f[v][0]) % mod)) % mod;
f[u][1] = f[u][1] * ((1 + f[v][1]) % mod) % mod; pre[u].push_back(1 + f[v][1]); suf[u].push_back(1 + f[v][1]);
}
for(int i = suf[u].size() - 2; i >= 0; i--) suf[u][i] = (suf[u][i + 1] * suf[u][i]) % mod;
for(int i = 1; i < suf[u].size(); i++) pre[u][i] = (pre[u][i - 1] * pre[u][i]) % mod;
suf[u].push_back(1);
// cout << u << " " << f[u][1] << " " << f[u][0] << "\n";
}
void dfs2(int u, int fa, int id){
int f0 = (g[fa][0] - ((f[u][0] + f[u][1]) % mod) + mod) % mod, f1 = id;
if(u != 1) g[u][0] = (f[u][0] + (f0 + f1)) % mod, g[u][1] = (f[u][1] * (1 + f1)) % mod;
else g[u][1] = f[u][1], g[u][0] = f[u][0], f1 = 0; int tot = 0;
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(v == fa) continue;
int fu0 = (g[u][0] - ((f[v][0] + f[v][1]) % mod) + mod) % mod, fu1 = (((1 + f1) * (tot ? pre[u][tot - 1] : 1) % mod) * suf[u][tot + 1] % mod) % mod;
int ansv = (f[v][1] + f[v][0]) % mod, ansu = (fu0 + fu1) % mod;
// cout << u << " " << v << " " << f[u][0] << " " << f[u][1] << " " << f0 << " " << f1 << " " << fu0 << " " << fu1 << "\n";
if(u == ans[edges[i].id].u) ans[edges[i].id].ansu = ansu, ans[edges[i].id].ansv = ansv;
else ans[edges[i].id].ansu = ansv, ans[edges[i].id].ansv = ansu;
dfs2(v, u, fu1); tot++;
}
}
signed main(){
//freopen("3.in", "r", stdin);
//freopen("my.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
int x, y; cin >> x >> y;
add_edge(x, y, i); add_edge(y, x, i);
ans[i] = {x, y, 0, 0};
}
dfs1(1, 0); dfs2(1, 0, 0);
for(int i = 1; i < n; i++) cout << ans[i].ansu << " " << ans[i].ansv << "\n";
//system("pause");
return 0;
}
/*
5
1 2
2 3
3 4
4 5
*/
T3 为了你唱下去
Statement:
给定一张有 \(n (1 \le n \le 10^5)\) 个点，有 \(m (1 \le 5 \times 10^5)\) 条带边权的边的无向图，其中 \(1 - c\) 是关键点。走过一条边会消耗该边边权大小的能量，如果当前能量小于边权则无法经过该点，但是到达关键点后又会将能量恢复到 \(r\)。现在问有多少非关键点可以从一个关键点出发，通过一条至少经过 \(k\) 个关键点的路径后到达。
\(30\)% 数据满足 \(n \le 500\)。
Solution:
图论好题。
首先容易发现两个关键点能够相互到达当且仅当两个点的最短距离小于等于 \(r\)。于是我们可以将关键点分为一些互不能到达且集合内部可以相互到达的集合。对于一个集合，我们可以先从任意点出发，走完里面的关键点后再去另外一个关键点。再由这些集合定义可知，只有集合大小大于等于 \(k\) 的集合才对答案有贡献。对于一个非关键点，若它与集合任一点的最短路径长度小于等于 \(r\)，则该节点可以通过路径走到。\(\rm Floyd\) 可以拿到 \(30pts\) 的高分。
考虑优化合并集合的过程。我们首先将所有关键点的距离标记为 \(0\)，跑一边 \(\rm Dijkstra\)，求出所有非关键点距离最近的一个关键点。枚举每一条边，对于一条边 \(i\)，若 \(w_i + dis[u] + dis[v] \le r\)，合并 \(u, v\) 所在的集合，并查集容易做到 \(O(m \log n)\)。
接着我们将所有所在集合大小大于等于 \(k\) 的集合的关键点的 \(dis\) 设为 \(0\)，再跑一遍 \(\rm Dijkstra\) ，计算 \(dis \le r\) 的点数即可。
qwq
#include<bits/stdc++.h>
#define int long long
#define pir pair<int, int>
using namespace std;
const int N = 1e5 + 10, M = 5e5 + 10, INF = 1e18;
int n, m, c, r, k, fa[N], siz[N], dis[N], vis[N], from[N];
struct edge{
int v, w, next;
}edges[M << 1];
int head[N], idx;
void add_edge(int u, int v, int w){
edges[++idx] = {v, w, head[u]};
head[u] = idx;
}
int findfa(int x){return fa[x] = ((x == fa[x]) ? x : findfa(fa[x]));}
void merge(int x, int y){
int fx = findfa(x), fy = findfa(y);
if(fx != fy){fa[fx] = fy; siz[fy] += siz[fx];}
}
void buildc(){
for(int i = 1; i <= n; i++) dis[i] = INF;
priority_queue<pir, vector<pir>, greater<pir> >Q;
for(int i = 1; i <= c; i++) dis[i] = 0, Q.push({0, i}), from[i] = i;
while(!Q.empty()){
pir p = Q.top(); Q.pop();
int u = p.second, dist = p.first;
if(vis[u]) continue; vis[u] = true;
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v;
if((!vis[v]) && dis[v] > dist + edges[i].w && dist + edges[i].w <= r){
dis[v] = dist + edges[i].w; from[v] = from[u];
// cout << v << " " << u << " " << dist + edges[i].w << "\n";
Q.push({dis[v], v});
}
}
}
for(int u = 1; u <= n; u++){
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v;
if(dis[v] + edges[i].w + dis[u] <= r) merge(from[u], from[v]);
}
}
}
void getans(){
for(int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false;
priority_queue<pir, vector<pir>, greater<pir> >Q;
for(int i = 1; i <= c; i++) if(siz[findfa(i)] >= k) dis[i] = 0, Q.push({0, i});
// for(int i = 1; i <= c; i++) cout << siz[findfa(i)] << "\n";
while(!Q.empty()){
pir p = Q.top(); Q.pop();
int u = p.second, dist = p.first;
if(vis[u]) continue; vis[u] = true;
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(edges[i].w > r) continue;
if((!vis[v]) && dis[v] > dist + edges[i].w){
dis[v] = dist + edges[i].w;
Q.push({dis[v], v});
}
}
}
int ans = 0;
for(int i = c + 1; i <= n; i++) if(dis[i] <= r) ans++;
cout << ans << "\n";
for(int i = c + 1; i <= n; i++) if(dis[i] <= r) cout << i << " ";
}
signed main(){
//freopen("ex_sample8.in", "r", stdin);
//freopen("my.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> c >> r >> k;
for(int i = 1; i <= m; i++){
int x, y, w; cin >> x >> y >> w;
add_edge(x, y, w); add_edge(y, x, w);
}
for(int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
buildc(); getans();
return 0;
}