日记 | 让不被看见的东西被看见

让那些隐匿于角落的微光，得以被众人看见

放假前的狂欢

五一长假要来啦！
已经忍不住的开心起来，这次假期不是很想回家，就在武汉探索探索吧。😄😄😄

英语小组pre

其中讲到了我们黄冈的东坡赤壁和青云宝塔。
其中关于青云塔上的那棵树，能一直向上生长真的很奇妙，于是我去查了查资料。
那是一棵朴树（不是平凡之路的那个朴树哈），首先它本身耐旱性就很强，依靠天然降水和空气湿度吸收水分就能够保证生存。
另外它的生长盘曲低矮，将根系深深扎入石缝里，形成一个“抱团共生”的样态。
据说它的种子是鸟类携带至塔顶，然后再于青瓦缝之间破“石”而出。
自然偶然性与生命韧性的有机结合🌱🌳

洛谷习题课

写在前面

其实这里都可以单独做一个数据结构学习板块了，考虑以后更新一下，暂时先放日记里吧~

树形dp

在此之前，先说另外一个重要知识点

链式前向星

核心点：用静态数据结构实现动态链表功能，既规避了动态内存管理的开销，又保留了链表的高效遍历特性

#include<iostream>
using namespace std;
const int maxn = 1e5;
const int maxm = 1e6;
struct edges
{
	int to;
	int next;
	int w;
}edges[maxm];
int first[maxn];//存储的是以每个节点为起始的最后一条边
int cnt = 0;

void add(int u, int v, int w)
{
	edges[++cnt].to = v;
	edges[cnt].w = w;
	edges[cnt].next = first[u];
	first[u] = cnt;
}

void visit(int u)
{
	for (int i = first[u]; i; i = edges[i].next)
	{
		cout << u << " " << edges[i].to << " " << edges[i].w << endl;
	}
}
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	visit(1);
	return 0;
}

链式前向星的五大核心优势​
​空间利用率​
链式前向星采用静态数组模拟链表，仅存储有效边信息（终点to、下一条边索引next、权重weight），空间复杂度为O(m)（m为边数）。相较于邻接矩阵的O(n)空间浪费，它在稀疏图中空间效率提升可达数百倍
​缓存友好性​
所有边数据在内存中连续存储，遍历时能充分利用CPU缓存预加载机制，相比邻接表（动态链表或vector）的分散存储，访问速度提升约30%-50%
​高效边添加操作​
采用头插法添加边，时间复杂度恒定为O(1)。邻接表的vector实现虽理论也是O(1)，但动态扩容会带来额外开销；邻接矩阵虽添加快但空间代价过大
​适合大规模稀疏图​
在社交网络、路由拓扑等场景下（边数m≪n），链式前向星的空间优势尤为明显
​静态结构的稳定性​
使用预先分配的数组，避免了动态内存分配和指针跳转的开销，适合需要频繁遍历图的算法（如Dijkstra、网络流）

回到树形dp

核心点是通过dfs遍历树结构，将问题拆解为子树的子问题，并且利用状态转移方程合并子结果。
例如在“没有上司的舞会”题目中：
f[u][0] = Σ max(f[v][0], f[v][1]) 不选u时的最大值
f[u][1] = Σ f[v][0] + val[u] 选u时的最大值

背包问题优化

在树形分组背包中，通过倒序遍历容量避免重复选择
状态dp[u][j]，它表示以结点u为根的子树上留j条边时的最多苹果数量

for (int j = Q; j >= 1; j--)  
    for (int k = 0; k <= j-1; k++)  //
        dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w);  //这里的u是父节点，v是子节点，w是v节点对应的权重

有一个讲的很清楚的微信公众号文章，其中关于这里j的递增还是递减讲的很清楚透彻。
算法竞赛专题解析（17）：DP应用–树形DP

放纵的金铲铲

谁能理解，从下午四点玩到晚上十点半的爽感啊。😍😍😍
越菜越爱玩，越玩越上头，越上头越菜(也是循环依赖上了哈)
考虑以后出个金铲铲攻略，推荐一下当下强势阵容(比如现在的五源韦鲁斯和圣灵薇古丝)
但九五还是yyds！😋