直径

发表于 2025-08-29

CF 1045D

树上任意两节点之间最长的简单路径即为树的「直径」。

可以用两次 DFS 或者树形 DP 的方法在
$O(n)$ 时间求出树的直径。

直接给出定理:在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。

cosnt int N=1e5+10;
int n,c,d[N];
vector<int> E<N>;
void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}

简单来说，是先任意找一端点，求出最长路径，那么找到的这个点一定是直径的一个端点，那么再做一次dfs就能找到另一个直径的端点。

求树上直径的点

int n, c = 0, t = 0, s = 0, mx = 0;
int d[N];
vector<int> e[N];
vector<int> path;

void dfs1(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        d[v] = d[u] + 1;
        if (d[v] > d[c]) c = v;
        dfs1(v, u);
    }
}

bool dfs2(int u, int fa) { // 寻找 t，并把路径 push 回溯
    if (u == t) {
        path.push_back(u);
        return true;
    }
    for (auto v : e[u]) {
        if (v == fa) continue;
        if (dfs2(v, u)) {
            path.push_back(u);
            return true;
        }
    }
    return false;
}

树形dp

我们定义
$dp[u]$ ：以
$u$ 为根的子树中，从
$u$ 出发的最长路径。那么容易得出转移方程：
$dp[u] = \max(dp[u], dp[v] + w(u, v))$ ，其中的
v 为
u 的子节点，
$w(u, v)$ 表示所经过边的权重。

constexpr int N = 10000 + 10;

int n, d = 0;
int dp[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    d = max(d, dp[u] + dp[v] + 1);
    dp[u] = max(dp[u], dp[v] + 1);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}
void solve(){
  cin >> n;
    clear_all();
    rep(i, 1, n - 1) {
        int u, v; cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 0);
    s = c;  //第一个端点
    d[s] = 0;
    dfs1(s, 0);
    t = c;   // 另一个端点
    dfs2(s,0);
    //d[c]代表mx
}

#include<bits/stdc++.h>
using namespace std;
vector<int>edge[100005];
int vis[100005];
int dis[100005];
void dfs(int st)
{
    for(int i=0;i<edge[st].size();i++)
    {
        int to=edge[st][i];
        if(!vis[to])
        {
            vis[to]=1;
            dis[to]=dis[st]+1;//注意，本代码计算的是无权树的直径，所以边权为1
            //如果是有权树，则这里的1要改为边权
            dfs(to);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;//n个点
    for(int i=1;i<=n-1;i++)//因为是树，有n-1条边
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);//无向图存储，若是有权树还要用结构体
    }
    dfs(1);//从1出发dfs一边
    int maxlen=0,Q,W,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(dis[i]>maxlen) maxlen=dis[i],Q=i;
        dis[i]=vis[i]=0;
    }//找到直径的一个端点Q
    dfs(Q);//从Q出发
    for(int i=1;i<=n;i++)
        if(dis[i]>ans) ans=dis[i],W=i;//找到另一个端点W，同时得到直径长度
    return 0;
}

链表

我们初始化链表的时候，要根据题目意思处理开头的第一个元素，这很重要！并且，我们把所有的指针都清成-1，这样保证了链表初始绝对合法。

//初始化
void init()
{
    for(int i=1;i<=n;i++)
        a[i].pre=a[i].nxt=-1;
    a[1].nxt=-1;
    a[1].pre=0;
    a[0].nxt=1;
}
//插入操作
void insert_left(int pos,int k)//把元素k插入到pos元素之前
{
    a[a[pos].pre].nxt=k;
    a[k].pre=a[pos].pre;
    a[pos].pre=k;
    a[k].nxt=pos;
}
void insert_right(int pos,int k)//把元素k插入到pos元素之后
{
    a[a[pos].nxt].pre=k;
    a[k].nxt=a[pos].nxt;
    a[pos].nxt=k;
    a[k].pre=pos;
}
//删除操作
void remove(int x)
{
    if(a[x].pre==-1)
        return;
    a[a[x].pre].nxt=a[x].nxt;
    a[a[x].nxt].pre=a[x].pre;
    a[x].pre=-1;
    a[x].nxt=-1;
}
//遍历
void print()
{
    int start=a[0].nxt;
    while(1)
    {
        printf("%d ",start);
        if(a[start].nxt==-1)
            break;
        start=a[start].nxt;
    }
}

p1160 模板

#include<bits/stdc++.h>
#define ll long long
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
using namespace std;
#define debug(a) cout<<#a<<"="<<a<<endl;
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
const int N=1e5+10;
int n;
struct node
{
    int nxt,pre;
}a[N];

void init(){
    rep(i,1,n){
        a[i].pre=a[i].nxt=-1;
    }
    a[1].nxt=-1;
    a[1].pre=0;
    a[0].nxt=1;
}
void insert_l(int pos,int k){//k insert pos left
    a[a[pos].pre].nxt=k;
    a[k].pre=a[pos].pre;
    a[pos].pre=k;
    a[k].nxt=pos;
}
void insert_r(int pos,int k){//k insert pos right
    a[a[pos].nxt].pre=k;
    a[k].nxt=a[pos].nxt;
    a[pos].nxt=k;
    a[k].pre=pos;
}
void remove(int x){
    if(a[x].pre==-1) return;
    a[a[x].pre].nxt=a[x].nxt;
    a[a[x].nxt].pre=a[x].pre;
    a[x].pre=-1;
    a[x].nxt=-1;
}
void print(){
    int start=a[0].nxt;
    while(1){
        cout<<start<<" ";
        if(a[start].nxt==-1) break;
        start=a[start].nxt;
    }
}
void solve()
{   
    cin>>n;init();
    rep(i,2,n){
        int k,p;cin>>k>>p;
        if(p==0) insert_l(k,i);
        else insert_r(k,i);
    }
    int m;cin>>m;
    rep(i,1,m){
        int x;cin>>x;
        remove(x);
    }
    print();
}
int main() {
    ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int _ = 1;
    //std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

Crypto

1、Hello crypto

解题思路：

非常简单的签到题。

import libnum
m = ...

flag = libnum.n2s(m)
print(flag)

2、EzAES

解题思路：

依旧是附件，据hint用utf-8编码打开（实际上直接用vscode打开就可）

题目直接给出了c iv key的具体值（这里的iv和key是随机生成的密钥）那么直接求解

from Crypto.Cipher import AES


key = b'\xf8\x0c"\xa0m\x94\xc0\xee\xd6\xd3zA\xf1+\xac\xc5'
iv = b'\xb8\xce418z\x8b\xb70\x80Q\xc3\xd6\xf6$\xdd'
c=b'\xa5\x94\xc6\x1a\xc8\xac\xef\x96\xdc\x11~F\xc1r\x14\xd1\x18\xf6\xe87\x80|\xc6<\xe3&\xa2T\x8a\xf4\xf8\xac\xbb\x82\xe7bv\x005\x90R\xd8\xea\x9f\x8e\xd3+\x8a'

my_aes = AES.new(key, AES.MODE_CBC, iv)

# 解密数据
decrypted_flag = my_aes.decrypt(c).rstrip(b' ')  # 移除填充的空格
print(decrypted_flag)

弯路：

显然刚用vscode打开时有点懵，不同于其他rsa加密，遂逐渐唤醒之前学过aes的记忆，尝试直接在线解密（因为不会写脚本），最后gpt大法！

3、d_known

解题思路:

读题，依旧是密文m 以及素数qp，但这里qp为相邻的素数，接着告知了d、c，直接开解

import math
import libnum
import gmpy2
import sympy

# 已知数据
d = ...
e = 0x10001
c = ...

ed1=e*d-1     #ed-1=k(p-1)(q-1)
for k in range(65537,1,-1):   #从65537开始递减
    if ed1%k==0:
        phi=ed1//k
        p1,s1=gmpy2.iroot(phi,2)#这里做的开放处理是因为近似qp相等
        p=gmpy2.next_prime(p1)
        if phi%(p-1)==0:
            q=sympy.prevprime(p)
            break
n=p*q
m=pow(c,d,n)
print(libnum.n2s(int(m)))

弯路：

整体过程异常曲折，首先重温rsa的基本加密步骤。附上一篇感觉写的很清楚的文章https://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html#:~:text=第一步，随机
1.怎么将qp表示出来
2.开方处理后怎么确保p-1 or q-1的范围是否跳脱了原本q和p的范围，即能不能确认这个next prime就是p or q，故尝试补上一些数，发现没用，最后结果并不用考虑…
3.k这个取值范围的考虑，一开始ai做出来的脚本大多都是递增，导致跑不出来，然后递减再做就ok了。

4、factor

解题思路：

这次告诉了N c e的值，依旧是rsa加密，那么从头开始看，定义proc函数，接着取10个任意64位质数作为prime_list，十个质数乘起来作为N，而从这十个选取7个相乘作为n，然后一切照旧。
步骤：1、分解N (yafu真好用)

2、列出n可能的情况进行求解

from itertools import combinations
from functools import reduce
from Crypto.Util.number import long_to_bytes, inverse

# 已知的 10 个素数
prime_list = [
    17179798839487874587,
    17734025616614438233,
    12381547806377025719,
    10734825458509712927,
    15542205590264116613,
    16197337718789165891,
    9878136298599787577,
    17628530333155146973,
    11044680896972316863,
    10017383368745005333
]

# 已知的公钥指数 e 和密文 c
e = 65537
c = 26766985375623703113904250876884598223156426789118183045142542215836711584140516370218654279179189004314203387292364759414400477630158

# 找到所有 7 个素数的组合
possible_combinations = list(combinations(prime_list, 7))

# 遍历每个组合，计算可能的 n 并尝试解密
for comb in possible_combinations:
    # 计算模数 n 和欧拉函数 phi_n
    n = reduce(lambda x, y: x * y, comb)
    phi_n = reduce(lambda x, y: x * (y - 1), comb, 1)

    try:
        # 计算私钥 d
        d = inverse(e, phi_n)

        # 尝试解密密文
        m = pow(c, d, n)

        # 将解密后的消息转换为字节形式
        plaintext = long_to_bytes(m)

        # 打印解密结果（可能的 flag）
        print(f"Possible flag with n = {n}: {plaintext.decode()}")

    except ValueError:
        # 如果计算 d 或解密失败，则跳过此组合
        continue

补充reduce函数：

1、reduce(lambda x, y: x * y, comb) 使用 Python 的 reduce 函数，对组合 comb 中的所有素数执行连续的乘法运算。
2、reduce(lambda x, y: x * (y - 1), comb, 1) 使用 reduce 函数，对组合 comb 中的每个素数 p进行p-1，即计算欧拉函数。

弯路：

1、寻找质数分解工具。在网上搜寻了好久，发现没有类似的中文在线网站可以分解这种质数，我甚至猜测是不是可以不用分解，发现不现实，但最后找到了yafu。
2、yafu的正确使用，这里贴上一些用法吧

1、如果数比较小，进入该文件的目录后可以直接使用：

yafu-x64 factor(23333333333333)
如果是powershell，则使用：

.\yafu-x64 factor(23333333333333)
2、如果数比较大，那就需要将数保存成一个txt，然后使用，powershell则是在前面加.\：

yafu-x64 “factor(@)” -batchfile n.txt

5、baby_mod

解题思路：

给出已知数leak r t 以及p q tmp的位数
那么已知tmp的位数很小，所以枚举非常好算。
tmp属于(2^14 2^15)这个范围;
又已知leak = pr - qt -tmp(leak为负数),
代换一下-leak-tmp = c1 =qt-pr(直接看做c1为常数);
接下来就是怎么解方程:
我们不妨设t1使得 t * t1 % r = 1,
上式两边同乘t1 再同取余r ,
便得到了q的表达式.
给出具体代码：

from Crypto.Util.number import long_to_bytes, inverse
from sympy import isprime, primerange
import libnum

# 已知的数据
c = ...
leak = -192....
r = ...
t = ...
e = 65537

tmp_list = list(primerange(2**14, 2**15))
for tmp_guess in tmp_list:
    c1 = -tmp_guess - leak
    if c1>0:
        t1 = libnum.invmod(t, r)  # 或者用 gmpy2.invert(r, t)
        q = (c1 * t1) % r  # 直接取模运算
        p = (t * q - c1) // r  # 计算 q
        if isprime(p) and isprime(q):
            n = p * q  # 得到模数 n
            phi = (p - 1) * (q - 1)  # 欧拉函数
            d = libnum.invmod(e, phi)  # 计算私钥 d
            m = pow(c, d, n)  # 解密
            print(libnum.n2s(m))  # 输出明文

弯路:

1、经过搜索其实是找到了相关的例题，贴下链接
https://blog.csdn.net/figfig55/article/details/128496397#:~:text=大概逻辑就是
但很明显，不能直接用，该题存在temp这一值，所以从头分析，就有了开头的代换，将未知转已知。
2、接着是两个if条件判断，但一开始我并未意识到这个leak这么小，所以我在设置c1>0后跑不出来flag，而程序检查也没有错误，最后发现要再颠倒一次，于是开头的c1略显诡异。

whi

直径

CF 1045D

树上任意两节点之间最长的简单路径即为树的「直径」。

求树上直径的点

树形dp

lists

链表

shctf

Crypto

1、Hello crypto

解题思路：

2、EzAES

解题思路：

弯路：

3、d_known

解题思路:

弯路：

4、factor

解题思路：

补充reduce函数：

弯路：

5、baby_mod

解题思路：

弯路: