树上差分,dfs栈,dfs做差,树上倍增
有8道题
A.
一棵含N个结点的树,有K条路径,求结点被经过的最大次数。
非常明显的树上差分:对于每一个节点i,都用pre[i]储存这个节点及其所有祖先节点的遍历次数,此时对每一条路径(u,v)进行分析:
- pre[u]++,pre[v]++;
- lca(u,v)只被遍历一次,但被加了两次, pre[lca(u,v)]—;
- lca(u,v)的祖先节点不会被遍历,但被加了两次(还剩一次),pre[par[lca(u,v)][0]]—;
得到代码如下:
1 |
|
树上差分,dfs栈,dfs做差,树上倍增
有8道题
一棵含N个结点的树,有K条路径,求结点被经过的最大次数。
非常明显的树上差分:对于每一个节点i,都用pre[i]储存这个节点及其所有祖先节点的遍历次数,此时对每一条路径(u,v)进行分析:
得到代码如下:
1 |
|
咕了很久,直到五一假期才来写qwq
莫名其妙地染上了拉丁瘾,都是因为Duolingo…(也可能是因为这本叫做《罗马十二帝王传》的八卦小册子)
很多人都推荐Wheelock,所以就找了一本来学。
说实话因为拉丁语已经死了,所以它的“发音”某种程度上并不重要,但是有些关于发音的符号还是很重要的。
书中表明应当把长音符号当作拼写的 部分来记忆,因为它所指示的发音区别往往对于含义极为关键(例如 Iiber 是名词,意为“书”,而 līber 是形容词,意为“自由的”)
动词;第一和第二变位法动词;现在时主动态的不定时、直陈式和命令式;翻译
和英语一样,拉丁语的动词有5个特征:人称 (persōna),数 (numerus),时态 (tempus),语气/式 (modus),语态 (vōx)。
拉丁语有3个人称(一,二,三),6个时态(现在时,将来时,未完成时,完成时,将来完成时,过去完成时),3种式(直陈式,命令式,虚拟式)以及2种语态(主动态,被动态)
总体来说和英语其实非常相似
Update your browser to view this website correctly.&npsb;Update my browser now