一些遇到的神奇技巧(?)
一些遇到的神奇技巧(?)
现在还很空，有遇到就填充。（本人学识疏浅，所以有‘?’）
所有证明请自行意会
C++语法类
-
scanf("%d/%d",&a,&b);可以读入 a , b 忽略 a b 之间的‘/’
如：input: 1/3 那么用上述代码输入后 a=1 , b=3
图论类
由于图论在oi里有很多分支，故有多个小标题
树
-
与树上某点最远的点一定是直径端点。
证明：把直径考虑成一条链，其他节点则长在连着这条链的树上，具体如下图：
那么如果有某一点的最远的点非直径两点，那么这个离它最远的点显然可以替换掉上图中的部分链（证明不是很严谨，意会） -
只改变一条边，树的直径至多改变一个端点
证明：假设新直径其中一个节点为s，与s距离最远的一点必为原直径其一端点，具体可以参考1的证明，所示1的广义情况应用。