text:
## Introduction

Motor deficits are common in patients with brain lesions and often have a great impact on the performance of activities of daily living (ADLs)1. Among different motor functions, gait and balance are critical in regaining independent ADL performance2,3. Therefore, it is expected that their improvement is the utmost priority in patients with brain lesions. Various measurement tools are used to evaluate the gait and balance functions such as the following: the 6-min walking test4, functional ambulation category (FAC)5, the Berg balance scale (BBS)6, and the modified Rankin scale7.

The BBS is a valid and reliable performance-based functional measurement test that evaluates various dynamic and static functional capabilities in the standing and sitting positions6. When using the BBS, the participant is asked to perform 14 various functional activities, such as sitting to standing, standing unsupported, reaching forward with an outstretched arm, turning 360°, and alternate stepping in succession onto an 8-inch platform6. Using a 5-point ordinal scale, from 0 to 4, the individual is scored based on the ability to maintain and perform the functional task6.

However, despite its apparent clinical utility, the BBS has some limitations that may complicate the interpretation of its scores and therefore discourage its use in guiding treatment planning for individuals with brain lesions. First, the BBS has both floor and ceiling effects8,9. Second, its inter-rater reliability is lower when assessing post-stroke individuals who score in the mid-range of the scale8,10. Third, the BBS score may be a poor predictor of post-stroke falls8,11,12,13. Finally, the score can improve without any actual improvement in the physiological function of standing balance8,12,13. Therefore, this score may not reflect the degree of motor function improvement after rehabilitation. Moreover, some individuals can achieve higher BBS scores by utilizing compensatory strategies and without recovering from actual dysfunctions12. Hence, individuals who achieve optimal BBS scores may still lack normal balance. Therefore, although it is a well-studied parameter that can evaluate the patients’ balance function, these limitations of the BBS score may limit its use in patients with brain lesions.

Another method in assessing balance impairments is the use of instruments, such as force plates14. However, similar to the BBS, certain measurements from force plates may display a combination of impairments and compensatory strategies. One compensatory strategy is to rely on the non-affected limb, while the affected limb is not actively contributing to standing balance control15. A measurement of center of pressure displacement, with both feet combined, may not identify such a compensatory strategy. A recent approach to assessing balance impairments in patients with brain lesions is the use of gait analysis16. In previous gait analysis studies, patients with brain lesions showed abnormalities in the control of body weight transfer toward the paretic limb side17,18. Gait analysis, unlike static foot plate application, is a dynamic evaluation method. The dynamic balance that can be observed may have more influence on the actual ADL performance than static balance19,20. Moreover, it is performed during actual gait and can identify compensatory strategies during the gait cycle. Hence, gait speed-related parameters in gait analysis may be correlated with the balance function of patients with brain lesions. However, its validity is not well established. Our hypothesis was that the gait speed- or step width-related parameters may be correlated with the balance function of patients with brain lesions. Therefore, this study aimed to clarify the relationship between the results of gait analysis and balance function, such as the BBS and seek specific measurements that can represent the balance functions of patients with brain lesions. Additionally, we compared other different gait function scale scores, such as the FAC or ambulation sub-score of the modified Barthel index (MBI) with gait analysis measurements.

## Methods

### Participants

We retrospectively reviewed the medical records of patients with brain lesions admitted to our hospital between January 2017 and August 2020.

The inclusion criteria were as follows: (1) age of ≥ 20 years; conditions with brain lesions, such as stroke, traumatic intracranial hemorrhage, or subarachnoid hemorrhage; and ability to walk independently; and (2) gait analysis and clinical assessment of the motor and gait functions, including the MBI, manual muscle test (MMT) of both lower extremities, FAC, and BBS. Conversely, the exclusion criteria were as follows: (1) > 1-week of interval between gait analysis and clinical assessment of the gait and motor functions; (2) patients who cannot walk without the use of walking aids, such as orthoses or a cane; and (3) history of other neurologic or orthopedic conditions that could affect the results of the study. This retrospective study was approved by ethics committee of the Ulsan University Hospital (2020-07-020) and was conducted according to the Declaration of Helsinki for human experiments. Written informed consent was obtained from all participants.

### Clinical assessment

Patient clinical records containing personal data, clinical diagnosis, time of the lesion, cognition (mini mental status examination [MMSE] score)21, ambulation and stair-climbing sub-score of the MBI22, MMT findings of both lower extremities, FAC, and BBS score were evaluated. All clinical assessments were performed by a physical therapist who was blinded to the gait analysis results.

Using the MMT findings of both lower extremities, we calculated the summation of the findings of both lower extremities (both hip flexor MMT + hip extensor MMT + knee extensor MMT + knee flexor MMT + ankle dorsiflexor MMT + ankle plantar flexor MMT; total, 60) and anti-gravity muscles in the lower extremities (both hip extensor MMT + knee extensor MMT + ankle plantar flexor MMT; total, 30)23. All clinical assessments were conducted by the patients’ primary physical therapist within 7 days of the gait analysis. All physical therapists performed the clinical assessments while blinded to the results of the gait analysis.

### Gait analysis

A computer-based instrumented gait analysis system (Walkway MG-1000, Anima, Japan) was used as the gait analysis system herein24. This gait analysis system can measure the spatiotemporal parameters of gait from on/off signals between the patients’ foot and the surface of the sensors at a sampling frequency of 100 Hz. The width and length of the walkway system are 0.82 m and 4.8 m, respectively24. In the walkway system, data were obtained and processed using the software embedded in the system.

### Experimental procedure

The participants were asked to wear short pants, get on a walking path, and walk barefoot along a 12-m straight line, including 3.5 m in front of the measured walking path and 3.5 m beyond the end of the walking path. No patient used braces or canes. Each participant performed one trial at a comfortable speed in a subjective manner24. The patients were asked to walk with their eyes facing forward, and their arms swinging naturally at the sides of the body. A physical therapist with > 10 years of experience performed the gait analysis of all the included patients.

### Gait analysis parameters

As the temporal parameters, the stance phase time (s), swing phase time (s), double stance phase time (s), ratio of the stance phase during the total gait cycle (%), ratio of the swing phase during the total gait cycle (%), ratio of the double stance phase during the total gait cycle (%), and stride time (s) were measured. As the distance parameters, the stride length (m), step length (m), and step width (m) were measured. Additionally, the gait angle (°), toe-out angle (°), gait speed (m/s), and cadence (step/min) were measured.

The gait angle was defined as the angle carried from the connected line of both heels between the right and left feet against the forward direction. The toe-out angle was defined as the open angle of a toe against the forward direction25.

Except for the stride length, stride time, gait speed, and cadence, the parameters were measured for each right and left lower extremity. For statistical analysis, we additionally calculated the average value of the parameters of the left and right sides, such as the average stance phase time (s), average swing phase time (s), average double stance phase time (s), average ratio of the stance phase during the total gait cycle (%), average ratio of the swing phase during the total gait cycle (%), average ratio of the double stance phase during the total gait cycle (%), average step length (m), average step width (m), average gait angle (°), and average toe-out angle (°). To compensate for differences in the patients’ height, we also calculated the gait speed/height, gait speed/height2, stride length/height, step length/height, step length/height2, stride length/height2, step width/height, step width/height2, stride time/height, and stride time/height2.

### Statistical analysis

The Kolmogorov–Smirnov test was used to determine whether the data conformed to a normal distribution. To identify the gait analysis parameters that would significantly correlate with the motor function (FAC, ambulation sub-score of the MBI, and BBS score), we performed a multiple linear regression analysis. To identify which variables would be affected by multicollinearity and the strength of the correlation, we tested for multicollinearity with variance inflation factors (VIFs). Multicollinearity may be present when the VIF is > 5 to 10. Thereafter, multiple linear regression tests were re-performed after removing parameters with multicollinearity. Statistical analyses were performed using SPSS (SPSS Inc., Chicago, IL).

## Results

### Patient characteristics

In this study, 77 patients with brain lesions (54 men and 23 women, 20–72 years of age, 139–185 cm in height, and 43–99 kg in weight) were investigated. Among them, 56 patients had ischemic stroke lesions; 8 patients had hemorrhagic stroke lesions; and 13 patients had traumatic brain injury. Of the patients, 64 had hemiparesis, and 13 had quadriparesis. All patients were admitted in the acute care hospital and underwent physical therapy of 1–2 sessions (30 min per one session) a day when performing gait analysis. The results of the clinical assessments and gait analysis are presented in Tables 1 and 2, respectively. The mean height, body weight, disease duration, total MBI, and MMSE scores were 165.17 ± 8.24 cm, 70.0 ± 12.69 kg, 34.40 ± 116.92 days, 80.67 ± 19.99, and 25.16 ± 6.68, respectively (Table 1). The average values of the summation of the total test scores were 55.72 ± 4.36 for the lower extremity muscle and 27.44 ± 2.76 for the anti-gravity lower extremity muscles (Table 2).

### Causal relationship between the balance function and gait analysis parameters

To evaluate the causal relationship between balance function and gait analysis parameters, the BBS score was used in multiple linear regression analysis. In the multiple linear regression analysis, the gait speed and average step width/height2 showed a significant correlation with the BBS score (p < 0.05) (Table 3, Fig. 1). However, the speed/height and speed/height2 showed multicollinearities; thus, they were removed from the multiple linear regression analysis. The equation for the BBS score and the gait analysis parameters was as follows:

$${\text{BBS score}} = 36.63 + \left( {0.55 \times {\text{gait speed }}\left[ {\text{cm/s}} \right]} \right) - \left( {1.05 \times {\text{average step width }}\left[ {{\text{cm}}} \right]/{\text{height}}^{2} \left[ {{\text{cm}}^{2} } \right]} \right)$$

### Causal relationship between the other physical performances and gait analysis parameters

In all the multiple linear regression analyses, the speed/height and speed/height2 showed a multicollinearity; thus, they were removed from such analyses.

Between the ambulation sub-score of the MBI and gait analysis parameters, only the gait speed showed a significant correlation with the ambulation sub-score of the MBI (p < 0.001) (Table 3). The equation for the ambulation sub-score of the MBI and the gait analysis parameters was as follows:

$${\text{Ambulation sub}} - {\text{score of the MBI}} = 3.41 + \left( {0.15 \times {\text{gait speed }}\left[ {\text{cm/s}} \right]} \right)$$

Between the stair-climbing sub-score of the MBI and gait analysis parameters, only the gait speed showed a significant correlation with the stair-climbing sub-score of the MBI (p < 0.001) (Table 3). The equation for the stair-climbing sub-score of the MBI and the gait analysis parameters was as follows:

$${\text{Stair - climbing sub}} - {\text{score of the MBI}} = - 2.99 + \left( {0.14 \times {\text{gait speed }}\left[ {\text{cm/s}} \right]} \right)$$

Between FAC and gait analysis parameters, only the gait speed showed a significant correlation with the FAC (p < 0.001) (Table 3). However, the speed/height and speed/height2 showed a multicollinearity; thus, they were removed from the multiple linear regression analysis. The equation for the FAC and the gait analysis parameters was as follows:

$${\text{FAC}} = 0.58 + \left( {0.39 \times {\text{gait speed }}\left[ {\text{cm/s}} \right]} \right)$$

Between the MMT findings of the lower extremities and gait analysis parameters, only the average swing phase time showed a significant correlation with the summation of the total MMT scores of the lower extremities (p < 0.05) (Table 3). The equation for the summation of the total MMT scores of the lower extremities and the gait analysis parameters was as follows:

$${\text{Summation of the total MMT scores of the lower extremities}} = 47.79 + \left( {16.45 \times {\text{average swing phase time }}\left[ {\text{s}} \right]} \right)$$

Moreover, only the average swing phase time showed a significant correlation with the summation of the MMT scores for the anti-gravity muscle of the lower extremities (p < 0.05) (Table 3). The equation for the summation of the MMT score for the anti-gravity muscle of the lower extremities and the gait analysis parameters was as follows:

$${\text{Summation of the MMT score for the anti}} - {\text{gravity muscle of the lower extremities}} = 24.04 + \left( {7.94 \times {\text{average swing phase time }}\left[ {\text{s}} \right]} \right).$$

## Discussion

The study showed that the BBS scores were significantly correlated with the gait speed and step width/height2. However, the other gait function measurements, such as the FAC and ambulation and stair-climbing sub-scores of the MBI, were correlated only with the gait speed. This difference may be because the other assessment tools, such as the MBI or FAC, are categorical. For example, of steps 1–5 for the FAC, only patients in steps 3, 4, and 5 will be able to undergo gait analysis. Additionally, of steps 1–5 for the ambulation or stair-climbing sub-score of the MBI, only patients in steps 4 and 5 will be able to undergo gait analysis. Therefore, the patients who can complete gait analysis would mostly be classified within 2–3 categories. Conversely, the BBS is a point assessment tool. Therefore, owing to its diversification, the step width/height2 could additionally be correlated with the BBS score.

Previously, Kobayashi et al.26 have reported similar results; the BBS score showed correlations with the gait speed, step length of the affected side, and stride length. However, all these three parameters were related to the gait speed. In contrast, our study showed additional correlations with the step width/height2. This difference may be attributed to the difference in the patient group and subject number. In their study, only eight patients with stroke wearing ankle–foot orthoses were enrolled. Moreover, in contrast with our study, several parameters that can be affected by the height or leg length were not corrected by the height or leg length. Therefore, the small number of participants and the non-correction with the height or leg length may have caused the difference with our results.

One interesting finding herein was that both the summations of the lower extremity MMT scores and the anti-gravity muscle MMT score of the lower extremities were correlated with the average swing phase time. We also evaluated the relationship between balance function and the results of gait analysis in hemiplegic patients with brain lesions. In hemiplegic patients, unlike whole patients, both the summation of the hemi-side lower extremity MMT scores and the summation of the antigravity muscle MMT score in hemi-side lower extremity were correlated with the hemi-side step length/height2 (Supplementary 1). However, in hemiplegic patients with brain lesions, the BBS score was correlated with gait speed (Supplementary 1). In previous studies, gait speed also has shown significant correlations with functional scale, such as the stroke impact scale (SIS) or physical domain of quality of life in patients with stroke27,28. However, the correlation with balance function was never studied. Interestingly, unlike the balance and gait functions, the lower extremity muscle strength did not show a correlation with the gait speed or step width, which may be associated with not only muscle strength but also other factors, such as proprioception of the lower extremities29,30.

Our study has several limitations. First, the patient group was heterogeneous. Further, the location of the brain lesions differed among the patients. The term brain lesion itself includes ischemic and hemorrhagic stroke lesions, in addition to traumatic intracranial hemorrhage. Therefore, we also evaluated the relationship between balance function and the results of gait analysis in hemiplegic patients with brain lesions. Interestingly, in both the whole patient group and the hemiplegic patient group, balance function was correlated with gait speed. However, further studies on a single lesion etiology are needed in the future to evaluate the relationship between balance function and gait analysis results. Second, patients with severely compromised gait function were excluded from this study. The participants were mandated to complete gait analysis; therefore, those with severe lower extremity motor dysfunction or balance dysfunction were not able to participate. Thus, the patients who had a balance function sufficient to measure the BBS score but were unable to walk were excluded from this study. As such, the study results cannot be generalized to all patients with brain lesions. Third, the patients underwent the gait analysis without any assistance, such as an ankle–foot orthosis or a cane. Therefore, our research results may not reflect the patients’ balance or gait function well if they improve their gait function with the help of an ankle–foot orthosis or a cane. Lastly, the spasticity was not considered in this study. Owing to the retrospective design of the study, spasticity was not sufficiently evaluated. Therefore, further studies are necessary to evaluate the effect of spasticity on balance function in patients with brain lesions.

## Conclusion

In the gait analysis, the gait speed may be an important factor in determining the balance and gait functions of the patients with brain lesions. Moreover, the step width/height2 may be a significant factor in determining their balance function. The balance function in patients with brain lesions plays a critical role in their ADL performance. Therefore, accurate evaluation of an individual’s balance function is important in predicting the prognosis and planning post-discharge treatment. Although the BBS is a well-known, well-proven evaluation tool for the balance function, it has its limitations. In such cases, using gait analysis parameters would be very helpful in assessing the current balance function status and planning further treatment strategies. Further studies with larger sample sizes should be performed to confirm this relationship.


text:
# Measurement of the forward $Z$ boson production cross-section in $pp$ collisions at $\sqrt{s}$ = 7 TeV

LHCb Collaboration; Aaij, R; Adeva, B; Adinolfi, M; Anderson, J; Bernet, R; Bowen, E; Bursche, A; Chiapolini, N; Chrzaszcz, M; Dey, B; Elsasser, C; Graverini, E; Lionetto, F; Lowdon, P; Mauri, A; Müller, K; Serra, N; Steinkamp, O; Storaci, B; Straumann, U; Tresch, M; Vollhardt, A; Weiden, A; et al (2015). Measurement of the forward $Z$ boson production cross-section in $pp$ collisions at $\sqrt{s}$ = 7 TeV. Journal of High Energy Physics, 2015(8):39.

## Abstract

A measurement of the production cross-section for $Z$ bosons that decay to muons is presented. The data were recorded by the LHCb detector during $pp$ collisions at a centre-of-mass energy of 7 TeV, and correspond to an integrated luminosity of 1.0 fb$^{-1}$. The cross-section is measured for muons in the pseudorapidity range $2.0 < \eta < 4.5$ with transverse momenta $p_{T} > 20$ GeV/c. The dimuon mass is restricted to $60 < M_{\mu^{+}\mu^{-}} < 120$ GeV/c$^{2}$. The measured cross-section is $$\sigma_{Z\rightarrow\mu^{+}\mu^{-}} = (76.0 \pm 0.3 \pm 0.5 \pm 1.0 \pm 1.3) \, \text{pb}$$ where the uncertainties are due to the sample size, systematic effects, the beam energy and the luminosity. This result is in good agreement with theoretical predictions at next-to-next-to-leading order in perturbative quantum chromodynamics. The cross-section is also measured differentially as a function of kinematic variables of the $Z$ boson. Ratios of the production cross-sections of electroweak bosons are presented using updated LHCb measurements of $W$ boson production. A precise test of the Standard Model is provided by the measurement of the ratio $$\frac{\sigma_{W^{+}\rightarrow\mu^{+}\nu_{\mu}} + \sigma_{W^{-}\rightarrow\mu^{-}\bar{\nu}_{\mu}}}{\sigma_{Z\rightarrow\mu^{+}\mu^{-}}}= 20.63\pm0.09\pm0.12\pm0.05,$$ where the uncertainty due to luminosity cancels.

## Abstract

A measurement of the production cross-section for $Z$ bosons that decay to muons is presented. The data were recorded by the LHCb detector during $pp$ collisions at a centre-of-mass energy of 7 TeV, and correspond to an integrated luminosity of 1.0 fb$^{-1}$. The cross-section is measured for muons in the pseudorapidity range $2.0 < \eta < 4.5$ with transverse momenta $p_{T} > 20$ GeV/c. The dimuon mass is restricted to $60 < M_{\mu^{+}\mu^{-}} < 120$ GeV/c$^{2}$. The measured cross-section is $$\sigma_{Z\rightarrow\mu^{+}\mu^{-}} = (76.0 \pm 0.3 \pm 0.5 \pm 1.0 \pm 1.3) \, \text{pb}$$ where the uncertainties are due to the sample size, systematic effects, the beam energy and the luminosity. This result is in good agreement with theoretical predictions at next-to-next-to-leading order in perturbative quantum chromodynamics. The cross-section is also measured differentially as a function of kinematic variables of the $Z$ boson. Ratios of the production cross-sections of electroweak bosons are presented using updated LHCb measurements of $W$ boson production. A precise test of the Standard Model is provided by the measurement of the ratio $$\frac{\sigma_{W^{+}\rightarrow\mu^{+}\nu_{\mu}} + \sigma_{W^{-}\rightarrow\mu^{-}\bar{\nu}_{\mu}}}{\sigma_{Z\rightarrow\mu^{+}\mu^{-}}}= 20.63\pm0.09\pm0.12\pm0.05,$$ where the uncertainty due to luminosity cancels.

## Statistics

### Citations

Dimensions.ai Metrics
69 citations in Web of Science®
81 citations in Scopus®

### Altmetrics

Detailed statistics

Item Type: Journal Article, refereed, original work 07 Faculty of Science > Physics Institute 530 Physics Physical Sciences > Nuclear and High Energy Physics English 2015 15 Feb 2016 11:37 26 Jan 2022 09:10 Springer 1029-8479 Gold Publisher DOI. An embargo period may apply. https://doi.org/10.1007/JHEP08(2015)039 http://arxiv.org/abs/1505.07024v2 (Organisation)

format: plain


text:
onsdag 25 november 2015

New Proof of Planck's Radiation Law vs (Italian) Piano Tuning

Computation Blackbody Radiation presentats a new approach to Planck's radiation law based on finite precision computation applied to a wave model consisting a set of harmonic oscillators with small damping subject to near-resonant forcing, each one of the oscillators of the form
• $\ddot u(t)+\nu^2u(t)+\gamma\dot u(t)=f(t)$ for time $t>0$,
where $\dot u=\frac{du}{dt}$ and $\ddot u=\frac{d^2u}{dt^2}$, $\nu >> 1$ is the eigenfrequency of the oscillator, $\gamma$ is a small positive damping coefficient with $\gamma\nu\le 1$, and $f(t)$ is a near-resonant forcing, for example given by
• $f(t)=\sin((\nu -0.5)t)+\sin(\nu t)+\sin((\nu +0.5)t)$
with a total frequency shift of 1 Hz.

A basic aspect of this model connects to the so called Italian tuning of a piano, where the three strings in the middle high register for each key/tone are tuned with a total frequency shift of about 1 Hz as above.

Let us now seek to understand in what sense Italian tuning is different from standard tuning with the three strings for each key/tone tuned to exactly the same frequency or pitch. We then identify in the above model
• the three strings are represented by the forcing $f(t)$,
• the sound board of the piano is represented by the oscillator,
• the outgoing sound from the sound board is represented by the damping.
Let us first consider standard tuning with strings and soundboard all with the same eigen-frequency, that is a case with perfect resonance. A pressed key activates a hammer with hits the strings which start to vibrate and thereby as forcing transfers energy to the sound board, which in turn starts to vibrate and produces a sound. In this case the forcing $f(t)$ will stay in phase with the velocity $\dot u$ over time, which means quick transfer of energy from strings to sound board as the integral of the positive product $f(t)\dot u(t)$ as the work performed per unit time. The result may be an outgoing sound of relatively high volume but short duration.

On the other hand, with the Italian tuning, the forcing from each of the three strings with slightly different frequencies cannot all be in phase with the common sound board velocity $\dot u$ over time, which means less quick energy transfer to the sound board with $f(t)\dot u(t)$ of changing sign and thus slower string energy loss as compared to the standard case. The result may be a sound of less volume but longer duration (sustain) than in the standard case, and also with slight "beat".

Of course, in reality it may be difficult to clearly separate the two cases, because perfect resonance does not really occur for a real piano with standard tuning, because of the complexity of the sound board, and also because the damper stops the string vibration before the tone has faded.

In any case, the distinction between perfect and near resonance is fundamental in the new proof of Planck's radiation law offered as by Computation Blackbody Radiation, a proof without reference to mystical statistics.

PS It is possible to change the setting by letting $f(t)$ represent the outgoing sound and the damping the input from the strings to the sound board. This is of relevance in stationary periodic state with sustained sound over long time without damping.

1 kommentar:

1. This is a really nice and understandable illustration on a topic that has been mystified and covered up in photon fog by "climate science"


text:
Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

D. 13th Labour of Heracles
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You've probably heard about the twelve labors of Heracles, but do you have any idea about the thirteenth? It is commonly assumed it took him a dozen years to complete the twelve feats, so on average, a year to accomplish every one of them. As time flows faster these days, you have minutes rather than months to solve this task. But will you manage?

In this problem, you are given a tree with $n$ weighted vertices. A tree is a connected graph with $n - 1$ edges.

Let us define its $k$-coloring as an assignment of $k$ colors to the edges so that each edge has exactly one color assigned to it. Note that you don't have to use all $k$ colors.

A subgraph of color $x$ consists of these edges from the original tree, which are assigned color $x$, and only those vertices that are adjacent to at least one such edge. So there are no vertices of degree $0$ in such a subgraph.

The value of a connected component is the sum of weights of its vertices. Let us define the value of a subgraph as a maximum of values of its connected components. We will assume that the value of an empty subgraph equals $0$.

There is also a value of a $k$-coloring, which equals the sum of values of subgraphs of all $k$ colors. Given a tree, for each $k$ from $1$ to $n - 1$ calculate the maximal value of a $k$-coloring.

Input

In the first line of input, there is a single integer $t$ ($1 \leq t \leq 10^5$) denoting the number of test cases. Then $t$ test cases follow.

First line of each test case contains a single integer $n$ ($2 \leq n \leq 10^5$). The second line consists of $n$ integers $w_1, w_2, \dots, w_n$ ($0 \leq w_i \leq 10^9$), $w_i$ equals the weight of $i$-th vertex. In each of the following $n - 1$ lines, there are two integers $u$, $v$ ($1 \leq u,v \leq n$) describing an edge between vertices $u$ and $v$. It is guaranteed that these edges form a tree.

The sum of $n$ in all test cases will not exceed $2 \cdot 10^5$.

Output

For every test case, your program should print one line containing $n - 1$ integers separated with a single space. The $i$-th number in a line should be the maximal value of a $i$-coloring of the tree.

Example
Input
4
4
3 5 4 6
2 1
3 1
4 3
2
21 32
2 1
6
20 13 17 13 13 11
2 1
3 1
4 1
5 1
6 1
4
10 6 6 6
1 2
2 3
4 1

Output
18 22 25
53
87 107 127 147 167
28 38 44

Note

The optimal $k$-colorings from the first test case are the following:

In the $1$-coloring all edges are given the same color. The subgraph of color $1$ contains all the edges and vertices from the original graph. Hence, its value equals $3 + 5 + 4 + 6 = 18$.

In an optimal $2$-coloring edges $(2, 1)$ and $(3,1)$ are assigned color $1$. Edge $(4, 3)$ is of color $2$. Hence the subgraph of color $1$ consists of a single connected component (vertices $1, 2, 3$) and its value equals $3 + 5 + 4 = 12$. The subgraph of color $2$ contains two vertices and one edge. Its value equals $4 + 6 = 10$.

In an optimal $3$-coloring all edges are assigned distinct colors. Hence subgraphs of each color consist of a single edge. They values are as follows: $3 + 4 = 7$, $4 + 6 = 10$, $3 + 5 = 8$.


text:
## Tuesday, December 30, 2014

### Mathematical Recreations : Ramanujan's Nested Radical

Srinivasa Ramanujan posed the following puzzle to the Journal of Indian Mathematical Society in April 1911.

What is the value of the following?
$$\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}}$$

He waited over six months, and when nobody replied he gave his solution. The result he provided was 3.

The algebraic solution provided by Ramunujan:

Consider the identity
$$(x+n)^2 = n^2 + 2nx + x^2 = n^2 + x[(x+n)+n]$$
Take square roots to get
$$[x+n] = \sqrt{n^2+x[(x+n)+n]}$$
Now inside the brackets you have (something + n), so you can
substitute in the same equation with (x+n) replacing (x) to get
$$x+n = \sqrt{n^2+x\sqrt{n^2+(x+n)[(x+2n)+n]}}$$
and repeat the process to get
$$x+n = \sqrt{n^2 + x\sqrt{n^2+(x+n)\sqrt{n^2+(x+2n)\sqrt{\cdots}}}}$$
If you now set n = 1, x = 2 you get
$$3 = \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}}$$

An alternate way of calculating the equation reveals some interesting behavior.

$$3 = \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}}$$
$$3^2 = 1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}$$
$$3^2-1= 2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}$$
$$\frac{3^2-1}{2}= \sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}$$
$$4 = \sqrt{1+3\sqrt{1+4\sqrt{1+5\sqrt{\cdots}}}}$$
$$\vdots$$
$$n = \sqrt{1+(n-1)\sqrt{1+(n)\sqrt{1+(n+1)\sqrt{\cdots}}}}$$

The value of each sequential nested radical forms a series...

$$3, 4, 5, 6, \cdots, \infty$$

...which is perfectly valid. If 3 was not a valid answer to the equation, then this calculation would have revealed a contradiction. Proof by contradiction is one of my favorite methods of proving.

$$4 = \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}}$$
$$\frac{3\cdot5}{2} = \sqrt{1+3\sqrt{1+4\sqrt{1+5\sqrt{\cdots}}}}$$
$$\frac{13\cdot17}{2^{2}3} = \sqrt{1+4\sqrt{1+5\sqrt{1+6\sqrt{\cdots}}}}$$
$$\frac{11\cdot19\cdot223}{2^{6}3^{2}} = \sqrt{1+5\sqrt{1+6\sqrt{1+7\sqrt{\cdots}}}}$$
$$\frac{17\cdot27902701}{2^{12}3^{4}} = \sqrt{1+6\sqrt{1+7\sqrt{1+8\sqrt{\cdots}}}}$$
$$\vdots$$

The value of each sequential radical forms another series.

$$4, 7.5, 18.41\bar6, 84.543402\bar7, 1429.71739065, \cdots, \infty$$

It is harder to predict subsequent entries of the series than for the original series, but no less valid. I've put some effort into constructing an algebraic function that also produces this series, but have set aside the challenge for now.

So, let's try another starting assumption.

$$2 = \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}}$$

The value of each sequential radical forms a third series...

$$2, 1.5, 0.41\bar6, -0.206597\bar2, -0.191463517554, \cdots, -\infty$$

...which is not valid under the convention that a radical can't have a negative value.

Generalizing this computation method, Ramanujan's Nested Radical has an infinite number of valid answers...

$$3 \ge \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}}$$

Every starting value greater than 3 results in a series of radical values that increase at more than 1 per step and increase to positive infinity. Every starting value less than 3 results in a series of radical values that increases at less than 1 per step and eventually turns negative. I don't yet know how to prove this general statement, but the pattern holds. The system behaves very simply when the starting value is 3, more than 3, or less than 3.

Ramanujan's solution to his puzzle is correct, but it is also incomplete.

The algebraic method is unable to find the full solution to the equation. Algebra doesn't effectively deal with infinites, so it shouldn't entirely be a surprise that an algebraic intuition might make some faulty (or at least incomplete) inferences when infinity is involved. This is interesting because it hints at the limits of algebra as a way of knowing truth. The Gödel Incompleteness Theorems discuss something similar to this and are worth reading more about.

How does this connect with biology?

One detail of my training to be a scientist is learning to look for untested assumptions in arguments that are presented to me. This was never explicitly stated in any of my graduate coursework, but it has been important to do well in the academic environment I experienced in getting my PhD. When I find such an assumption, I see it as a puzzle to be explored. Am I seeing something real? What inferences is the presenter drawing from the assumption? Why is what I'm seeing not already addressed?

What assumptions have you made today?

References:
1. Ramanujan: www.thefamouspeople.com/profiles/srinivasa-ramanujan-503.php
2. Algebraic solve: mathforum.org/library/drmath/view/52674.html
5. Incompleteness theorems: en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems

## Saturday, December 27, 2014

### Mystery Plant ID Found!

 1. omnilexica.com/?q=silphium
A little over a year ago, I was involved in a wedding party and we were walking through a park to a site for some of the arranged photographs. Along the walk, we crossed a stream and there I came across an interesting plant.

The plant was done flowering, but the seed heads retained a nice green color and had the lovely geometry seen in image #1. I picked a sample of the plant, using the pocket-knife I almost always carry (largely for such purposes as this).

Neither myself, my mother, nor my aunt were able to identify the plant. Now this was getting interesting, as my mother and aunt have a long history of gardening and interest in wildflowers. My aunt noted the material had the scent of sunflowers, but this only helped identify it to the family level, which the structure itself had already provided. I tucked the sample into my pocket, hoping to keep it intact until I could identify it at some later time. On returning home, I consulted the field guides I owned. I had no luck, since they all seem to focus on the most charismatic aspect of the wildflowers…  usually, the flowers themselves.

As the plant material dried, I realized that I had collected very mature looking seeds of this unknown plant. I cleaned the seeds and stored them in a vial, hoping to identify them when I later had the chance to grow plants from them. Part of the motivation was also because I thought that the green seed heads would make a nice display in a vase, so I could use the plant as part of my home flower cutting garden.
 2. diggingdog.com/pages2/plantpages.php/P-1403

…a year passes…

I am in the final stages of completing my PhD thesis and found my mind wandering. I was reading about the efforts to breed perennial versions of annual crops and to domesticate new perennial crops from wild plants. While looking through a document on the efforts to generate perennial seed crops, I saw a dried plant specimen of Silphium integrifolium (Deam's Rosinweed) and it struck a memory. A quick web-search later and I found an image of exactly what I discovered on the creekside. However, there are several potential species in the genus Silphium that live in the area and have the memorable seed heads, so it will still take growing the seeds I saved to identify the plant down to the species level.

The plant was being studied for its domestication potential as a new seed crop. I still think it would be a worthwhile project to domesticate it as green material for florist use. Domestication of a single plant species can easily go in multiple directions at once, as the plethora of cabbage/broccoli/etc. plants indicate.

Now that I know what the plant looks like and that it will produce some really nice flowers (image #2), I can better plan for where the plant will go in my garden next year.

References:

## Tuesday, December 23, 2014

### GMO labeling : The right to know what is in our food.

Sometimes biology intersects with political-charged topics that engage large-numbers of people. In the USA, there has been recent activity around the labeling of foods made from genetically modified organisms (GMOs). The following video epitomizes one viewpoint on the subject.

http://www.upworthy.com/a-14-year-old-explains-food-labeling-in-language-even-condescending-tv-hosts-should-get-3?c=reccon3

One of the major arguments presented in the video is that people have the right to know what is in our food. Because of this, GMO foods should be labeled.

I think this is a wonderful idea!

However… there's a big problem. People think they know what is in regular crops, while they think they don't know what is in GMO crops. Can you list the compounds found in the last organic heirloom tomato that you ate? Do you know what is in "natural" corn? How about the poisons found in the various types of beans that people eat? How about the poisons sprayed on any crops (even organic) that you might find in the store? The reality is that people, in general, have no idea what is in any of the food they eat.

A second problem I have is that the GMO-labeling ideas being pushed will do nothing to assist people in knowing what is in their food. If you're eating a tomato which included a gene from a fish and the label only says the tomato has been altered with a certain form of technology, then the label does nothing at all to inform you about what you're eating.

We do already have an established method for indicating the presence of small amounts of diverse substances in our food that can be utilized for labeling GMOs: the ingredients list. If your tomato product also includes some fish genes, then the ingredients list for the tomato should include the fish (and any bacterial) genes that are found in it. Finding an ingredients label on a single tomato will discourage those who aren't interested in purchasing GMOs, but will allow those who are interested in learning what is in their food to be able to easily educate themselves.

So far, no organization is pushing for such an educational labeling idea. The people pushing for GMO-labeling don't want honest and educational labeling. They're pushing for labels to inspire fear, uncertainty, and doubt (FUD) about GMOs.

I think such a labeling system should also be extended to indicate what chemicals were sprayed on the fruit and thus are likely to remain on the fruit. This issue doesn't involve GMOs, but these chemicals are something we do know with certainty are poisons...  and yet there is no push for this information on labels.

I am a biologist, so I realize my perceptions of this subject are likely to be distinct from those of most people.

I agree with the reasons stated for GMO labeling, but I am totally against every GMO-labeling proposal I have so far heard being discussed because they don't help attain the goal of the stated reasons.

## Monday, December 15, 2014

### Hybrid sunflower roots.

 1. Plant 3, roots & tuber.
A few weeks ago, we had a solid freeze and the sunflower season came to an end. I dropped by the old place and dug up my sunflowers to see if any of the F1s had developed tubers. The largest hybrid (plant 3) produced one skinny tuber, while the smaller two plants appeared to produce no tubers at all. This was a disappointment, but a more detailed examination of the remaining plant material led to some positive surprises.

 2. Plant 1, seeds.
The first plant looked very much like the Helianthus tuberosus mother, but with more red pigment on the stems. I had assumed this was the result of some recombination of maternal alleles and was at best a control to compare the hybrid plants against. When I looked at the remaining two dried flowers on this plant and found them to be full of seeds (image #2), I realized this plant is likely to also be a hybrid.
 3. Plant 3, root bud.

The plant that grew the tuber in image #1 also produced a second type of perennial structure, a new bud growing from the old root crown (image #3). This is a structure that isn't seen in either parent species. This feature has been observed before in crosses of this type, however, so I should have expected the possibility.

 4. Plant 2, roots.
The other two plants had mildly-swollen roots (images #4 & #5) that have appeared alive when I checked on them. I don't know if they will show new growth in the spring, or if the roots will at some point finally start to rot.
 5. Plant 1, roots.

I'm storing the tuber and all the root structures in a dedicated small cube-fridge over the winter. This should keep them safe from the mice that wander through my basement and allow me to grow at least one of them again next year alongside additional F1s from the ~70 seeds that remain from the first cross.

References:
1. H. annuss x H. tuberosus : bulbnrose.x10.mx/Heredity/sunflowerXchoke/sunflowerXchoke.html

## Wednesday, December 10, 2014

I've recently written a new post on the topic of toxicity in this plant that you should also read if you've found this page via search or other methods.

 1. Solanum nigrum.
Myths of edibility are much shorter-lived than myths of toxicity. If something is poisonous and you keep eating it, you (or your surviving friends and relatives) will soon learn your error. If something is perfectly edible, but you never eat it for fear of poison, then you will never learn what you're missing.

The common weedy plant Solanum nigrum (Black Nightshade) is a premiere example of this. The berries are routinely considered to be poison, even though there are no recorded fatal poisonings unambiguously associated with the plant.

The berries of every S. nigrum plant I've come across have been very edible, tasting like a somewhat floral and mildly sweet tomato. The ripe berries and green leaves are used over much of the world, with the leaves being used as a pot-herb comparable to spinach. Research has suggested that it might not be a good idea to eat the unripe berries, as they sometimes contain a limited amount of solanine.

Plant poisons tend to be polite, in that they have the trait of tasting poisonous. The putative toxin in S. nigrum is solanine, which has a bitter taste. There are reports of some S. nigrum plants having bitter leaves and unpleasant berries, while others have bland leaves and mildly sweet berries. I suppose I should advise you to not eat the unpleasant tasting plants.

The myth of toxicity of S. nigrum seems to have been spread by the European diaspora. European-derived cultures everywhere seem to think it is deadly poison, even while the natives living in the same places continue eating it routinely. Why would Europeans think this plant is poison?

 2. Atropa belladonna; UK range map.
In the UK and much of western Europe, there grows another plant with black berries. This one, Atropa belladonna (Deadly Nightshade), is deadly poisonous, with a long recorded history of deaths… but only in Europe where it grows. In Europe, if you taught children that one black berry (S. nigrum) was edible, but another (A. belladonna) was poison, there would be the risk of them making a deadly mistake in identification. In this context, it is perfectly reasonable for European parents to teach their children that black berries are poison.

A. belladonna has spread to a few other places in the world, but isn't something you will generally run into. If you don't know plants well enough to tell the difference between S. nigrum and A. belladonna, then you really shouldn't be eating anything you find outside. The plants are as distinct as a dog is from a cat. You almost assuredly have experience with identifying those animals, so there is absolutely no way you would mistake one for the other. It still is a good idea to teach children not to eat things you can't identify, but you shouldn't be claiming poison is the reason.

 3. Diospyros texana.
The aversion to black berries has even carried over to entirely unrelated plants, that just happen to have black, round fruit.

Diospyros texana (Texas Persimmon) is a tree that produces perfectly edible black fruit that many (of European cultural extraction) consider to be poisonous, even though there are no toxic relatives or mimics. It has a long history of utilization as a food source by American natives of the arid Southwest, but has in recent times been marginalized to a landscaping plant because of the peculiar attitudes of the now-dominant culture.
 4. S. nigrum.

Forms of S. nigrum have been partly domesticated under the name "Garden Huckleberry". These plants have slightly larger berries and a more upright growth form than most of the wild plants. There are red ("Makoi") and orange ("Otricoli") varieties that people might be more likely to believe are edible.

I've collected numerous seeds from a local (Minnesota) form of S. nigrum, with the goal of using them in a mutation breeding experiment. The basic idea is to expose a batch of seeds to some mutagen, like X-rays or some chemicals, and then grow out the resulting plants to look for variations which might be more useful. Larger or different colored fruit are the most obvious things to look for, but other interesting traits may also appear. I would like to use ultraviolet light as a source of mutations, as UV-light is easy to control and keep contained, but I still need to determine if it will work for these seeds.

There are still occasional reports of people eating S. nigrum and experiencing gastrointestinal distress. They could have had a specific allergic reaction to the new food source. For this reason, people should be conservative about eating plants they don't have experience with.

 5. Solanine-rich S. dulcamara.
The putative poison found in S. nigrum is the bitter-tasting solanine. It is not entirely clear if everyone can taste this compound. You can experimentally determine your ability to taste Solanine by tasting the very common S. dulcamara (image #5), which has elongated orange/red berries and purple flowers. S. dulcamara is definitely toxic due to the high levels of solanine found in its leaves and berries. For several years, I have been occasionally tasting the berries (looking for a 'sweet' version), but have found very little variation in the amount of poison. If the fruit of this plant tastes sweet to you, then you should have someone else taste it before you really eat any and you might want to avoid tasting wild things like this as a rule.

If you eat some S. nigrum (or S. dulcamara) berries and get sick, you really can't blame me for it. "Some guy on the internet told me it was ok!" won't hold up in court.

References:

## Tuesday, December 2, 2014

### Nicotine

Nicotine is highly addictive, and not just for us humans.

I observed this black vulture (Coragyps atratus) apparently looking for and eating discarded cigarettes at a roadside park in central Florida. I also noted the same behavior with a different group of vultures at another park during the same trip.

If we were to eat tobacco like this, it would quickly make us sick. Vultures are adapted to eat decaying meat and all the nasty toxins that go with it. Because of this, they have what would be described as an, "iron stomach". I wonder how common the behavior is and if addicted vultures get angry when they haven't had a fix in too long.

Cigarette butts have reportedly been found in the intestines of whales (presumably having been washed out to the ocean and ingested along with their normal food). There are photos of other birds investigating cigarette butts they come across, but I haven't found any reports of any animals actually eating them.

(While trying to find other reports of this behavior, I did find a report of people smoking dried vulture brains. People are strange things.)