首页 > 其他分享 >【实变函数】03 - 可测函数

【实变函数】03 - 可测函数

时间:2023-05-03 18:34:38浏览次数:37  
标签:实变 03 underset 可测 函数 mu 收敛 测度

  上篇在\(\sigma\)-环上延拓了测度的概念,并讨论了实数轴上典型的可测集\(\mathbf{L},\mathbf{L^g},\mathbf{B}\)。这些理论精巧而有其独立性,但还需放到合适的领域里才能展现其本质和威力。\(\sigma\)-环是个普遍的代数结构,它的可列交并运算特别适用于需要级数运算的场合,这也将是我们建立新的积分理论的核心工具。以下再来回顾一下新的积分理论的基本思想。

  对取值为实数的函数\(f(x)\)(定义域可以为一般集合),黎曼积分是将定义域分割为若干连续片段,要求每个片段上的函数值相近,以此进行累加。新的积分思想则是将值域分割为若干区间\([y_i,y_{i+1})\),然后考察每个值区间原象\(E_i\)的测度,并依次进行累加(式(1))。两种积分都可以看成是加权级数,前者以函数值为权重赋在定义域上,而后者则以原象的测度为权重赋在值域上。黎曼积分虽然直观,却不如新积分触及到积分的本质,从而理论中有诸多限制和不便。以下便逐步展开新积分的定义和性质。

\[S=\sum_{i=0}^n\xi_i\mu(E_i);\;\;y_i\leqslant\xi_i<y_{i+1},\,E_i=E(y_i\leqslant f(x)<y_{i+1})\tag{1}\]

1. 可测函数

1.1 定义和一般性质

  新积分中要求对任何值区间\([y_i,y_{i+1})\),其原象\(E_i\)都要有测度。这里我们需要放缓脚步,把原象集\(E_i\)和测度先分开考虑,因为测度是可以后来赋予的。先从纯粹集合论的角度,定义清楚我们的讨论对象,比如我们期望原象集\(E_i\)能组成\(\sigma\)-环,以便自由地进行交并运算。为此,在基本空间\(X\)上的任意集类\(\mathbf{R}\),如果它是\(\sigma\)-环,我们便称\((X,\mathbf{R})\)是可测空间,其元素\(E\in\mathbf{R}\)称为\((X,\mathbf{R})\)上的可测集。这里的“可测”二字即抛开了具体的测度定义,而关注集合论上的通用性质。
  进而,如果函数\(f(x)\)的原象\(E=E(c\leqslant f(x))\)总是\((X,\mathbf{R})\)上的可测集,\(f(x)\)便称为\((X,\mathbf{R})\)上的可测函数。当然,这里的\(c\leqslant f(x)\)可以换成\(c< f(x),f(x)\leqslant c,f(x)<c\)或者任何一种区间,都会得到等价的定义,后面我们将不加区别地使用它们。当\(X\)取实数集\(E^1\),\(\mathbf{R}\)取\(\mathbf{L},\mathbf{L^g},\mathbf{B}\)时,相应地就是 Lebesgue 可测集(函数)、Lebesgue-Stieltjes 可测集(函数)、Borel 可测集(函数)。请特别注意:本篇除明确指出外,都是在一般可测空间上的讨论。

• 求证:定义在区间上的连续函数,一定是Lebesgue可测函数。

  不难证明,可测函数\(f(x)\)的定义域\(E\)一定是可测集,\(f(x)\)在任意可测子集\(E_i\subset E\)上还是可测函数。以及更多在定义域的交并运算上推导出的结论,都没有根本性的困难。反过来,函数在值域上的代数运算,是否还是可测函数,这需要一点细致的讨论。比如\(f,g\)都是可测函数,要证明\(E(c<f(x)+g(x))=E(f(x)>c-g(x))\)是可测集,可将其拆分为式(2)的等价定义。其中\(r_i\)是全体有理数的一个排列,这里用到了有理数的可列可数性和稠密性。另外容易证明,对任意实数\(a\),\(af(x)\)也是可测函数,所以可测函数的线性和还是可测函数。

\[E(c<f+g)=\bigcup_{i=1}^\infty(E(f>r_i)\cap E(g>c-r_i)) \tag{2}\]

  继续看函数乘除运算的情况。对乘法\(f(x)g(x)\),可以先证\(f^2(x)\)是可测函数,再使用等式\(fg=[(f+g)^2-(f-g)^2]/4\),便知\(f(x)g(x)\)也是可测函数。对除法\(f(x)/g(x)\),只要先证\(1/g(x)\)是可测函数,便知\(f(x)/g(x)\)也是可测函数。最后还不难证明,\(\min(f(x),g(x)),\max(f(x),g(x))\),以及\(|f(x)|=\max(f(x),-f(x))\)都是可测函数。至此便知,可测函数的一般代数运算仍然是可测函数。

1.2 函数列极限

  函数列极限是积分中的一个重要课题,有必要先讨论这些极限函数是否为可测函数。首先,\(\{f_n(x)\}\)的上确界函数\(F(x)\)其实是式(3)的极限函数,式(4)说明\(F(x)\)是可测函数。由此也不难证明,\(\{f_n(x)\}\)的下确界函数也是可测函数。记\(G_n(x)\)为\(f_n,f_{n+1},\cdots\)的上确界函数,则易知\(G_1\geqslant G_2\geqslant G_3\geqslant\cdots\)都是可测函数。式(5)说明\(f_n(x)\)的上限函数是\(\{G_n(x)\}\)的下确界,故而也是可测函数,同样可证下限函数\(\underset{n\to\infty}{\underline\lim}f_n(x)\)也是可测函数。进而如果极限\(\underset{n\to\infty}\lim f_n(x)\)存在,它也是可测函数。

\[F(x)=\lim_{n\to\infty}F_n(x),\;F_n(x)=\max\{f_1(x),\cdots,f_n(x)\}\tag{3}\]

\[E(c<F(x))=\bigcup_{n=1}^\infty E(c<F_n(x))\tag{4}\]

\[\underset{n\to\infty}{\overline\lim}f_n(x)=\lim_{n\to\infty}G_n(x)\tag{5}\]

  以上关于函数极限的结论,要求各种极限是存在的(极限为有限实函数)。其实如果把\(\pm\infty\)也包含在实函数的定义中,并不会产生冲突和意外,甚至在表述上还会更加简练。作为函数极限的一个举例,我们来构造可测函数列\(\{f_n(x)\}\),以逼近给定的可测函数\(f(x)\)。思路非常直观,先将值域分成若干长度为\(\dfrac{1}{n}\)的区间\(E_i^n\)(式(6)),构造函数\(f_n(x)\)在\(E_i^n\)的值都是\(\dfrac{i}{n}\)。\(f_n(x)\)其实是由若干特征函数构成,且不难证明\(\underset{n\to\infty}\lim f_n(x)\to f(x)\)。这个结论的关键价值不是函数列的存在性,而是\(E_i^n\)只有可列个。

\[f_n(x)=\sum_i\dfrac{i}{n}\chi_{E_i^n},\;\;E_i^n=E\left(\dfrac{i}{n}\leqslant f(x)<\dfrac{i+1}{n}\right)\tag{6}\]

  最后来讨论一个比较综合问题,当是对本段内容的一个回顾。我们知道\(\mathbf{B}\in\mathbf{L}\),所以Borel可测函数一定是Lebesgue可测函数。反过来也可以证明,一个定义在\(E\)上的Lebesgue可测函数\(f(x)\),“稍作修改”后也可以是Borel可测函数。先如上面构造\(f(x)\)的逼近函数列\(f_n(x)\),然后对每个Lebesgue集\(E_i^n\)存在Borel集\(B_i^n\subset E_i^n\),且\(m(E_i^n-B_i^n)=0\)。如果以\(B_i^n\)构造函数列\(h_n\),则它们都是Borel可测的,且易知\(m(f_n\ne h_n)=0\),然后不难证明式(7)。为了构造Borel可测函数,在定义域上一定要小心论证,这里还需要找到Borel集\(B_0\supset E_0,E(B_0)=0\),然后在\(B_1=E^1-B_0\)上定义\(h(x)\)(式(8),\(B_0\)上补零)。这样的\(h(x)\)才是Borel可测函数,且在\(E-B_0\)上收敛于\(f(x)\),即有\(m(E(f\ne g))=0\)。

\[\lim_{n\to\infty}h_n(x)\to f(x),\;x\in E-E_0,\,E_0=\bigcup_{n=1}^\infty E(f_n\ne h_n)\tag{7}\]

\[h(x)=\lim_{n\to\infty}h_n(x)\chi_{B_1}(x),\;\;B_1=E^1-B_0\tag{8}\]

2. 可测函数列的收敛

2.1 基于测度的两种收敛

  现在是时候在可测空间\((X,\mathbf{R})\)上引入测度,并继而在测度上计算积分。现假定引入的测度为\(\mu\),则称\((X,\mathbf{R},\mu)\)为测度空间。其中\(\mu\)可能是有限测度、全有限测度、\(\sigma\)-有限测度、\(\sigma\)-全有限测度等。然而在讨论积分之前,需要把零测度给讨论带来的问题边界梳理清楚。因为零测度对积分或其它问题的讨论不构成本质影响,我们大可以抛开这部分定义域,而使得讨论对象超出可测函数的范围。以下讨论两种在测度上“近似”的函数极限,以及它们之间的关系。

  当讨论\(E\subset X\)(不一定有\(E\in\mathbf{R}\))上的一个命题\(P\)时,如果存在测度为零的集\(E_0\)(不一定有\(E_0\subset E\)),使得命题在\(E-E_0\)上成立,则我们说命题\(P\)在\(E\)上几乎处处成立(或概成立)。留意括号中的两个注释,这里讨论的对象可以不是“可测”的,后续讨论中我们将得到更完满的结局,即找到“零测度差”的可测对象。另外还要强调,定义是基于某个测度\(\mu\)的,因此用代数式表示时命题时,一定要有测度标识。比如几乎处处相等\(f(x)\underset{\mu}{=}h(x)\)、几乎处处收敛\(\underset{n\to\infty}\lim f_n(x)\underset{\mu}{\to}f(x)\)等。

  然而虽然讨论中会出现非“可测”的对象,可测集(函数)还是我们讨论的主要对象、以及很多结论的必要条件,这时我们需要细致妥当地处理好那个零测度的误差,用可测函数“替换”不可测函数。比如已知可测函数列\(\{f_n(x)\}\)在\(E\)上几乎处处收敛,可以先记在\(E-E_0\)上收敛于可测函数\(\tilde{f}(x)\)(所以需要函数列可测),然后再补零扩展为\(E\)上的可测函数\(f(x)\),这时便有\(\underset{n\to\infty}\lim f_n(x)\underset{\mu}{\to}f(x)\)。再假定已知可测函数列\(\underset{n\to\infty}\lim f_n(x)\underset{\mu}{\to}h(x)\)(\(h(x)\)不一定可测),可挖去的零测度集为\(E_1\),则显然在\(\left(E-E_0\cup E_1\right)\)上有\(f(x)=h(x)\),也就是说存在可测函数\(f(x)\)使得\(f(x)\underset{\mu}{=}h(x)\)。

  关于可测函数列的收敛,还有一种条件更弱、更常用的收敛定义。对\(E\)上可测函数列\(\{f_n(x)\}\),如果存在函数\(f(x)\)(不一定可测),对任何\(\varepsilon>0\)都有式(9)成立,则称函数列依测度收敛或度量收敛)于\(f(x)\)。这种收敛的误差集随着\(n\to\infty\)逐渐收敛于零测度,而不同于几乎处处收敛的限定于一个零测度集\(E_0\)上。然而说几乎处处收敛强于依测度收敛,却又是不太准确的。前者更强调单点上的最终收敛,后者则更强调误差测度的趋零性,请自行构造满足其一而不满足另一个例子。

\[f_n(x)\underset{\mu}{\Rightarrow}f(x) \;\Leftrightarrow\;\underset{n\to\infty}\lim\mu(E(|f(x)-f_n(x)|)>\varepsilon)=0\tag{9}\]

2.2 两种收敛的关系

  明白两种收敛的本质后,便能容易地找到它们的关联。比如已知可测函数列\(\{f_n(x)\}\)依测度收敛于\(f(x)\),即\(f_n(x)\)与\(f(x)\)的“偏差集测度”越来越小。我们一定可以从中挑选出子列\(\{f_{n_i}(x)\}\),使得“偏差集测度”被限制在“充分小”的集合上,从而子列处处收敛于\(f(x)\)。这是分析学的常用方法,具体来说,取\(\varepsilon=\delta=\dfrac{1}{2^i}\),则存在\(n_i\)使得满足式(10)的\(\varepsilon-\delta\)条件。记式中的误差集为\(E_i\),不难证明在\(F=\underset{i\to\infty}{\overline\lim}E_i\)之外,子列处处收敛于\(f(x)\)。再由\(\underset{i=1}{\overset{\infty}{\sum}}E_i\)有限,可证\(\mu(F)=0\),从而最终有\(\{f_{n_i}(x)\}\)几乎处处收敛于\(f(x)\)。

\[\mu\left(E(|f_n(x)-f(x)|>\dfrac{1}{2^i})\right)<\dfrac{1}{2^i},\;n\geqslant n_i\tag{10}\]

  这个结论可以帮助得到依测度收敛的简单性质。比如因为存在几乎处处收敛的子列,\(f(x)\)在\(E-F\)上就是可测函数,它可以修改为\(E\)上的可测函数\(h(x)\),即有\(f(x)\underset{\mu}{=}h(x)\)。而且任何满足\(f_n(x)\underset{\mu}{\Rightarrow}g(x)\)的收敛函数都有\(g(x)\underset{\mu}{=}h(x)\)。但要注意,暂时还不能证明\(f_n(x)\underset{\mu}{\Rightarrow}h(x)\),“可替换性”要用下面构造的基本函数列证明。

  反过来,如果\(\{f_n(x)\}\)几乎处处收敛于\(f(x)\),为讨论方便先假定\(f(x)\)是可测函数。则存在\(\mu(E_0)=0\)使得函数列在\(E_1=E-E_0\)上处处收敛于\(f(x)\),这其实等价于式(11)(有必要复习上下限函数的意义和不等式)。如果\(\mu(E)=\mu(E_1)\)是有限的,根据不等式不难得知\(\mu(E_1(|f_n-f|>\varepsilon))\)是趋于零的,从而\(\{f_n(x)\}\)依测度收敛于\(f(x)\)。也就是说,当\(\mu(E)<\infty\)时,几乎处处收敛的确是比依测度收敛更强的条件。最后利用上面的替换法,这里\(f(x)\)是可测函数的条件可以拿掉,而结论换成可测函数\(h(x)\underset{\mu}{=}f(x)\)。

\[E_1=\underset{n\to\infty}{\underline\lim}E_1(|f_n(x)-f(x)|<\varepsilon),\;\;\varepsilon>0\tag{11}\]

  以下继续假定\(\mu(E)<\infty\),如果可测函数列\(\{f_n(x)\}\)不依测度收敛于可测函数\(f(x)\),则可以从中选出子列\(\{f_{n_i}(x)\}\)(“误差集测度”恒\(>\delta\)),使其没有依概率收敛的子列,从而也没有几乎处处收敛的子列。综合以上,\(\{f_n(x)\}\)依测度收敛于\(f(x)\)的充要条件是,对任何\(\{f_{n_i}(x)\}\)都能再找到几乎处处收敛于\(f(x)\)的子列。利用这个结论不难证明,依概率收敛的函数列(\(\mu(E)<\infty\)),它们的简单代数运算也是依概率收敛的(式(12),写出证明)。

\[f_n\underset{\mu}\Rightarrow f,\,g_n\underset{\mu}\Rightarrow g\;\mapsto\;af_n+bg_n\Rightarrow af+bg,\,f_ng_n\Rightarrow fg,\,f_n/g_n\Rightarrow f/g\tag{12}\]

  在数列的极限中,往往用柯西数列(基本数列)代替极限的判断条件,因为它不需要极限点在场,使用起来更加方便。在依测度收敛中,也可以定义类似的收敛函数列,即对任意\(\varepsilon>0\),可测函数列\(\{f_n(x)\}\)在下标足够大后满足式(13)。称这样的函数列为依测度的基本函数列,或简称基本函数列。依测度收敛的函数列显然是基本函数列,反之对于基本函数列\(\{f_n(x)\}\),可以先证明存在子列\(\{f_{n_i}(x)\}\)依测度收敛于某可测函数\(f(x)\),再证得\(\{f_n(x)\}\)依测度收敛于\(f(x)\)(请自行证明,注意\(\mu(E)\)不一定有限)。

\[E(|f_n(x)-f_m(x)|)<\varepsilon,\;\;m,n>N\tag{13}\]

  选择子列的方法仍然是我们熟悉的基本分析技巧,即选出的下标使得“偏差测度”以指数递减(式(14))。不难证明,在\(F=\underset{i\to\infty}{\overline\lim}E_i\)之外,子列处处收敛且有\(\mu(F)=0\),即子列几乎处处收敛于某可测函数\(f(x)\)。这就证明了依测度收敛和基本函数列的等价性。证明中还间接说明了,基本函数列以测度收敛于某可测函数\(f(x)\)。如果预先知道函数列依测度收敛于\(h(x)\)(不一定可测),那么它一定是基本函数列,继而可知\(h(x)\underset{\mu}{=}f(x)\),这就是依测度收敛的“可替换性”了。

\[E_i=E(|f_{n_i}(x)-f_{n_k}(x)|)<\dfrac{1}{2^i},\;\;k>i\tag{14}\]

2.3 一致收敛和连续性

  收敛的一致性是许多性质的来源,我们现在证明,几乎处处收敛的函数列也是“近乎”一致收敛的。具体来说,如果可测函数列\(\{f_n(x)\}\)几乎处处收敛到\(f(x)\),则对任意\(\delta>0\)存在可测集\(E_{\delta}\),使得\(\mu(E-E_\delta)<\delta\)且函数列在\(E_{\delta}\)上一致收敛于\(f(x)\)。证明没有本质难度,又是那个“一尺之棰,日取其半,万世不竭”的把戏。先是定义式(15)的“误差范围内子集”,几乎处处收敛即表示极限\(\underset{n\to\infty}\lim\mu(E_{n,k})=\mu(E)\)成立(假定在\(E\)上处处收敛,因为零测度误差很好处理)。因此对任何\(\varepsilon=\dfrac{1}{k}\),总存在下标\(n_k\)使得式(16)成立,不难证明集合\(\underset{n=0}{\overset{\infty}{\bigcap}}B_{n_k,k}\)就是我们要找的\(E_{\delta}\)。

\[B_{n,k}=E\left(|f_m(x)-f(x)|<\dfrac{1}{k},\;m\geqslant n\right)\tag{15}\]

\[\mu(E)-\mu(B_{n_k,k})<\dfrac{\delta}{2^k}\tag{16}\]

  连续性是很多函数列收敛性质的关键,然而基于测度的连续就不能也不必像数学分析里那样严苛了。设\(f(x)\)为点集\(E\)上的函数,其中一点\(x_0\in E\),如果对任意\(\varepsilon>0\)都存在\(x_0\)的邻域\(|x-x_0|<\delta,\,x\in E\),使得\(|f(x)-f(x_0)|<\varepsilon\),则称\(x_0\)是\(f(x)\)的连续点。如果所有\(x\in E\)都是连续点,则\(f(x)\)称为连续函数。比如有理数域的常量函数,再比如闭集上的常量函数,请自行证明。另外类似数学分析中的证明,如果\(E\)上的连续函数列\(\{f_n(x)\}\)一致收敛于\(f(x)\),则\(f(x)\)也是\(E\)上的连续函数。

  最后来看一个Lebesgue可测函数的惊人事实。设\(f(x)\)是\(E\)上的Lebesgue可测函数,先假定\(m(E)\)有限,将其分成式(17)的可数个子集。根据\(m(E)\)有限,可先剔除掉\(|n|>n_k\)的子集并确保式(18)左足够小,然后在剩下的子集中作闭集\(F_{n,k}\)使得式(18)右成立。在闭集\(F_k=\bigcup F_{n,k}\)上作特征函数\(f_k(x)\)(\(F_{n,k}\)上的值为\(\dfrac{n}{k}\)),它们显然是连续函数。最后在闭集\(F=\bigcap F_k\)上观察,\(f_k(x)\)连续且一致收敛于\(f(x)\),从而\(f(x)\)在\(F\)上是连续函数!由于\(\mu(E-F_k)\)可以任意小,再次使用“日取其半”的方法,对任意\(\delta>0\)都能找到\(\mu(E-F)<\delta\)。

\[E_{n,k}=E\left(\dfrac{n}{k}\leqslant f(x)<\dfrac{n}{k}\right),\;n=0,\pm 1,\pm 2,\cdots\tag{17}\]

\[\underset{|n|>n_k}{\sum}m(E_{n,k})<\delta;\;\underset{|n|\leqslant n_k}{\sum}m(E_{n,k}-F_{n,k})<\delta\tag{18}\]

  当\(\mu(E)=+\infty\)时,可以把直线\(E^1\)分割成可列个不相交的有限区间\((a_k,b_k]\),在每个子集\((a_k,b_k]\cap E\)上对\(\dfrac{\delta}{2^k}\)使用刚才的结论。最终得知结论在\(\mu(E)=+\infty\)上也成立,它被称为鲁津定理。由于\(F\)是闭集,那么\(E^1-F\)就是开集,连接每个开集区间的端点(属于\(F\)),便得到了整个\(E^1\)上的连续函数\(h(x)\)。所以有鲁津定理的一种形式:设\(f(x)\)是\(E\)上的Lebesgue可测函数,对任意\(\delta>0\)都存在\(E^1\)上的连续函数\(h(x)\),使得\(m(E(f\neq h))<\delta\)。

标签:实变,03,underset,可测,函数,mu,收敛,测度
From: https://www.cnblogs.com/edward-bian/p/16388900.html

相关文章

  • 自定义函数实现分组统计
    1.通过自定义的函数实现分组统计: 2.自定义函数,对索引进行修改取不同产品名称的数量: ......
  • 【实变函数】04 - 基于测度的积分
    1.有限有界积分1.1积分及存在性有了前两篇的铺垫,现在可以顺理成章地定义积分的概念了。和Riemann积分一样,定义要分成两步,先是在有限定义域的有界函数上,然后使用极限法推广到一般函数上。具体来说,设\(E\)是某测度空间的有限可测集(\(\mu(E)<\infty\)),\(f(x)\)是\(E\)上的有界......
  • 【实变函数】05 - 积分极限和乘积测度
    1.积分的极限积分与极限运算的交换,是数学分析中的重要工具。但在Riemann积分中,运算交换需要较强的条件,特别是麻烦的“一致收敛性”。然而“一致收敛性”并不是运算交换的必要条件,但是从Riemann积分的定义出发,却很难再有进一步的弱化条件。本篇你将看到,在基于测度的积分上,极......
  • 对一列或多列使用聚合函数
    1.根据产品名称获取分组对象 2.对不同的列采用不同的聚合函数 ......
  • 【实变函数】01 - 更合理的积分
    【本系列目录】   01- 更合理的积分   02- 测度论基础   03-可测函数   04-基于测度的积分   05-积分极限和乘积测度   06- 导数与单调函数   07- 微积分基本定理  08-广义测度和积分  博客总目录 1.源起......
  • 【实变函数】02 - 测度论基础
    1.测度和\(\sigma\)-环在上一篇我感受到,对复杂集合的描述都是很困难的事,更不好定义一个清晰普遍的测度。正确的思路应该是,从可以定义测度的简单集开始,合理地向外扩展,直至包含足够丰富的集。这样即满足了复杂性要求,也同时兼容了简单集的测度。所谓简单集,就比如实数集上的区间......
  • Ruby安装错误:in `encode': U+00CD to IBM437 in conversion from UTF-16LE to UTF-8 t
    解决方法:去本地路径下修改编码,这么提示是因为编码不一致导致的。  修改registry文件中的编码:  修改后就没有问题了。 来源:https://www.cnblogs.com/py-tiger/p/5372258.html......
  • AI 作画火了,如何用 Serverless 函数计算部署 Stable Diffusion?
    作者:寒斜立即体验基于函数计算部署StableDiffusion:https://developer.aliyun.com/topic/aigcAIGC领域目前大火,除了Chatgpt,在文生图领域StableDiffusion大放异彩,深刻的地影响着绘画、视频制作等相关领域。利用这项技术,普通人也可以制作出令人惊叹的艺术作品。今天我们将......
  • 2.八数码II(搜索进阶 IDA*估价函数 + 迭代加深)
    八数码II↑题目链接题目在一个\(3×3\)的网格中,\(1∼8\)这8个数字和一个X恰好不重不漏地分布在这\(3×3\)的网格中。例如:123X46758在游戏过程中,可以把X与其上、下、左、右四个方向之一的数字交换(如果存在)。把X与上下左右方向数字交换的行动记录为u......
  • 「解题报告」ARC103D Distance Sums
    给Kaguya看了一眼,Kaguya用了一分钟切了。我看了一个小时。这就是神吗。考虑一个点往叶子走答案的贡献,显然距离和会变化\(-siz_u+(n-siz_u)=n-2siz_u\)。如果我们以重心为根,那么所有的\(n-2siz_u>0\),那么这实际上是一个小根堆。那么我们考虑从大往小枚举叶子,然......