简单树上问题の笔记

树上差分,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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=100005;

ll n,k;
vector<ll> e[N];

ll par[N][25];
ll dep[N];

ll ans;

void dfs(ll x,ll f)
{
par[x][0]=f;
for(auto y:e[x])
{
if(y==f)
{
continue;
}
dep[y]=dep[x]+1;
dfs(y,x);
}
}


ll LCA(ll x,ll y)
{
if(dep[x]>dep[y])
{
swap(x,y);
}

for(ll i=0;i<20;i++)
{
if((dep[x]-dep[y])>>i&1)
{
y=par[y][i];
}
}

if(x==y)
{
return x;
}

for(ll i=19;~i;i--)
{
if(par[x][i]!=par[y][i])
{
x=par[x][i],y=par[y][i];
}
}

return par[x][0];
}

ll pre[N];

void dfs2(ll x,ll f)
{
for(auto y:e[x])
{
if(y==f)
{
continue;
}

dfs2(y,x);
pre[x]+=pre[y];
}

ans=max(ans,pre[x]);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

cin>>n>>k;
for(ll i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;

e[x].push_back(y);
e[y].push_back(x);
}

dfs(1,0);
for(ll j=1;j<20;j++)
{
for(ll i=1;i<=n;i++)
{
par[i][j]=par[par[i][j-1]][j-1];
}
}

while(k--)
{
ll x,y;
cin>>x>>y;

ll l=LCA(x,y);
pre[x]++,pre[y]++;
pre[l]--,pre[par[l][0]]--;
}

dfs2(1,0);

cout<<ans<<"\n";

return 0;
}


【笔记】Wheelock's Latin 001

咕了很久,直到五一假期才来写qwq

莫名其妙地染上了拉丁瘾,都是因为Duolingo…(也可能是因为这本叫做《罗马十二帝王传》的八卦小册子)

很多人都推荐Wheelock,所以就找了一本来学。


发音相关

说实话因为拉丁语已经死了,所以它的“发音”某种程度上并不重要,但是有些关于发音的符号还是很重要的。

  • 拉丁语中元音的发音有长和短两种,长音用长音符号(字母上方的短横)标出(比如ā)

书中表明应当把长音符号当作拼写的 部分来记忆,因为它所指示的发音区别往往对于含义极为关键(例如 Iiber 是名词,意为“书”,而 līber 是形容词,意为“自由的”)

  • 还有就是重音符,书中说会标明,因为希望读者可以学会正确的朗读拉丁语词汇

第一课

动词;第一和第二变位法动词;现在时主动态的不定时、直陈式和命令式;翻译

动词 (verbum)

和英语一样,拉丁语的动词有5个特征:人称 (persōna),数 (numerus),时态 (tempus),语气/式 (modus),语态 (vōx)。

拉丁语有3个人称(一,二,三),6个时态(现在时,将来时,未完成时,完成时,将来完成时,过去完成时),3种式(直陈式,命令式,虚拟式)以及2种语态(主动态,被动态)

总体来说和英语其实非常相似

变位 (coniugāre)

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×