\(T1\)
题目描述
给定一棵 \(n\) 个节点的树，求前 \(m\) 条最长路径的长度。
数据范围
序号 \(n\) \(m\) 数据类型
1 10 3 暴力
2 233 23333 暴力
3 2000 300000 暴力
4 2000 300000 暴力
5 50000 1 随机生成
6 7798 17798 随机生成
7 7798 27798 随机生成
8 7798 37798 随机生成
9 50000 300000 1-n 顺序输入的链
10 50000 300000 以 1 为根的菊花图
\(Solution\)
估分：\(70\)
实测：\(40\)
因为写链时脑子抽了居然用了 \(map\) 然后空间炸了，还有判断是否是链那里写错了一点导致第一个点还挂了。。。
对于链：先把 \(1-i(i <= n)\) 的所有链加入堆，然后取出最大的输出，再把这条链删掉上面那条边，扔进堆里
对于菊花图：把每条边排个序，可以构造一个矩形，矩形的 \((x, y)\) 代表的是 \(d[x] + d[y]\) ，\(d[i]\) 是 \(i\) 到 \(1\) 的边权，先把第一行全部扔进堆里，取最大的输出，再把 \((x + 1, y)\) 上的值扔进去
对于暴力：枚举每条链，用 \(LCA\) 维护链的长度
正解：点分治，把每棵子树做超级钢琴的做法，用 \(st\) 表或者线段树维护
\(Code\)
不知道如何下手...照着网上的一篇题解打的
#include<bits/stdc++.h>
#define F(i, x, y) for(int i = x; i <= y; ++i)
using namespace std;
int read();
const int N = 5e4 + 5;
int n, m;
int sum, root, mx, id, l, r;
int head[N], cnt, ver[N << 1], edge[N << 1], nxt[N << 1];
int st[N * 20][21], d[N * 20], size[N], vis[N], dis[N];
struct node{
int l, r;
}p[N * 20];
struct use{
int l, r, h, mq;
};
priority_queue<use> q;
bool operator<(use a,use b)
{
return d[a.h] + d[a.mq] < d[b.h] + d[b.mq];
}
void add(int x, int y, int z)
{
ver[++ cnt] = y, edge[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;
}
void get_root(int x, int fa)
{
size[x] = 1; int maxn = 0;
for(int i = head[x]; i; i = nxt[i])
{
int y = ver[i];
if(vis[y] || y == fa) continue;
get_root(y, x), size[x] += size[y], maxn = max(maxn, size[y]);
}
maxn = max(maxn, sum - size[x]);
if(maxn < mx) mx = maxn, root = x;
}
void dfs(int x, int fa)
{
d[++ id] = dis[x], p[id] = {l, r};
for(int i = head[x]; i; i = nxt[i])
if(! vis[ver[i]] && ver[i] != fa)
dis[ver[i]] = dis[x] + edge[i], dfs(ver[i], x);
}
void solve(int x)
{
vis[x] = 1, d[++ id] = 0, p[id] = {0, 0}, l = r = id;
for(int i = head[x]; i; i = nxt[i])
if(! vis[ver[i]])
dis[ver[i]] = edge[i], dfs(ver[i], x), r = id;
for(int i = head[x]; i; i = nxt[i])
if(! vis[ver[i]])
root = 0, sum = size[ver[i]], mx = INT_MAX, get_root(ver[i], 0), solve(root);
}
int query(int l, int r)
{
int k = log2(r - l + 1);
return d[st[l][k]] > d[st[r - (1 << k) + 1][k]] ? st[l][k] : st[r - (1 << k) + 1][k];
}
void pre()
{
F(i, 1, id) st[i][0] = i;
F(j, 1, 20)
F(i, 1, id - (1 << j) + 1)
if(d[st[i][j - 1]] > d[st[i + (1 << j - 1)][j - 1]]) st[i][j] = st[i][j - 1];
else st[i][j] = st[i + (1 << j - 1)][j - 1];
F(i, 1, id)
if(p[i].l) q.push(use{p[i].l, p[i].r, i, query(p[i].l, p[i].r)});
}
int main()
{
n = read(), m = read();
for(int i = 1, x, y, z; i < n; ++ i) x = read(), y = read(), z = read(), add(x, y, z), add(y, x, z);
sum = n, mx = INT_MAX, get_root(1, 0), solve(root), pre();
F(i, 1, m)
{
use k = q.top(); q.pop(), printf("%d\n", d[k.mq] + d[k.h]);
if(k.mq - k.l) q.push(use{k.l, k.mq - 1, k.h, query(k.l, k.mq - 1)});
if(k.r - k.mq) q.push(use{k.mq + 1, k.r, k.h, query(k.mq + 1, k.r)});
}
return 0;
}
int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
\(T3\)
题目描述
星球上有 \(n\) 个城市，标号为 \(1-n\)，用 \(n-1\) 条双向通道连接，保证任意两个城市能互相到达。
生化危机爆发了！但由于*安全能力有限，安全区只包括在标号 \(l\) 到 \(r\) 的城市，你现在在城市 \(x\)，想知道最近的安全城市的距离。
数据范围
对于 \(30\%\) 的数据, \(n，q<=1000\)；
另有 \(20\%\) 的数据，保证第城市 \(2-n\) 均可直接到达城市 \(1\)；
另有 \(10\%\) 的数据，保证城市 i(1<=i<=n-1)可直接到达城市 \(i+1\)；
对于 \(100\%\) 的数据, \(n，q<=100000\)，\(li<=ri\)，任意两个城市的距离小于 \(10^9\)。
\(Solution\)
估分：\(60\)
实测：\(60\)
对于链：如果在 \([l \ ,\ r]\) 里输出 \(0\)，不在则取 \(min(d[x][l] \ , \ d[x][r])\)，\(d[i][j]\) 表示 \(i \ , \ j\) 之间距离
对于菊花图：用 \(st\) 表维护 \(l-r\) 的每个点到 \(1\) 的路径的 \(min\) 值，分情况讨论即可
对于其他：直接 \(dfs\) ，加个剪枝，当当前距离大于 \(ans\) 时返回，可以水过此题
正解：要用到点分治还是点分树来着，我分不太清这两个，大概就是，拆成很多个子树，在每个子树上都做一个动态加点线段树，维护此子树里在 \(l-r\) 中的点到子树根的最小值，用此最小值加上子树根到 \(x\) 的值，更新 \(ans\)，然后再往上跳，找新的子树根
\(Code\)
（正解只存在于口胡233
#include<bits/stdc++.h>
#define ll long long
#define F(i, x, y) for(int i = x; i <= y; ++i)
using namespace std;
ll read();
const int N = 1e6 + 5;
const int M = N << 1;
const ll inf = 1e18 + 5;
int n, q, flag;
ll x, y, z, l, r, ans;
ll head[N], cnt, ver[M], nxt[M];
ll edge[M], d[N], st[N][22], ok[N];
void add(ll x, ll y, ll z)
{
ver[++ cnt] = y, edge[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;
}
void dfs1(int x, int fa)
{
for(int i = head[x]; i; i = nxt[i])
if(ver[i] != fa)
d[ver[i]] = d[x] + edge[i], dfs1(ver[i], x);
}
void solve_1()// 链
{
dfs1(1, 0);
while(q --)
{
l = read(), r = read(), x = read();
if(x < l) printf("%lld\n", d[l] - d[x]);
else if(x > r) printf("%lld\n", d[x] - d[r]);
else puts("0");
}
exit(0);
}
void solve_2()// 菊花图
{
F(i, 2, n) st[i][0] = edge[head[i]];
F(j, 1, 20)
for(int i = 1; i + (1 << j) - 1 <= n; ++ i)
st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
while(q --)
{
l = read(), r = read(), x = read();
int k = log2(r - l + 1);
if(x <= r && x >= l) puts("0");// 如果 x 安全，则输出 0
else if(l == 1) printf("%lld\n", edge[head[x]]);// 如果 1 安全，直接输出到 1 的距离
else if(x == 1) printf("%lld\n", min(st[l][k], st[r - (1 << k) + 1][k]));// 如果要求的是 1，则直接找一个最小值
else printf("%lld\n", edge[head[x]] + min(st[l][k], st[r - (1 << k) + 1][k]));// 剩余情况
}
exit(0);
}
void dfs3(ll x, ll fa, ll dis)
{
if(dis >= ans) return;
if(x >= l && x <= r)
{
ans = min(ans, dis);
return;
}
for(int i = head[x]; i; i = nxt[i])
if(ver[i] != fa)
dfs3(ver[i], x, dis + edge[i]);
}
void solve_3()// 其他
{
while(q --)
{
l = read(), r = read(), x = read();
ans = inf, dfs3(x, 0, 0);
printf("%lld\n", ans);
}
}
int main()
{
n = read();
F(i, 1, n - 1)
{
x = read(), y = read(), z = read(), add(x, y, z), add(y, x, z);
if(abs(x - y) > 1) flag = 1;
}
q = read();
if(! flag) solve_1();
F(i, 2, n) if(ver[head[i]] != 1) flag = 0;
if(flag) solve_2();
solve_3();
return 0;
}
ll read()
{
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}