CF2023E Tree of Life
不会 1C，破防去看 1E，大战 1.5h 无果，破防*2，下大分。
神秘贪心题，赛时只想对了一半不到。
写这题题解前先安利一道思路比较类似的树上覆盖问题（P7246 手势密码），做完这两道题应该会对这类问题有一定启发？
如何设计一个合理的贪心策略？首先第一个思路肯定是从下往上解决问题，肯定设
不如设现在考虑到了点
- 新开一个路径。
- 从
v_i 子树中拿出一条向上的路径延长一步与从v_j 子树中拿出一条向上的路径延长一步拼起来。
自然的，一个新的定义出现了：设
继续考虑如何计算
这个算法看上去很对，实际上，这是错误的！！！
举个例子，对于一个
如何修正这个想法呢？不如考虑先让所有向上的路径在
可能看到这里你已经晕了。重新书写一下所有的定义：
设
考虑如何进行转移，同样地，先考虑解决新的边二元组的问题。
如果
在满足新的边二元组后，同样的，有初值
显然的，我们的目的是要对这些路径进行拆分重组，使尽量多的路径结合在一起，即让
这个问题比较麻烦，因为可以将
先考虑一个弱化的问题，现在有
结论是：
先假设
-
若
a_n\ge \sum_{i=1}^{n-1}a_i ，那么最大操作次数是\sum_{i=1}^{n-1}a_i 。 -
若
a_n< \sum_{i=1}^{n-1}a_i ，那么最大操作次数是\lfloor \frac{\sum a_i}{2}\rfloor 。
证明其实非常简单，首先第一种情况是显然的，主要证第二种情况，设
这个问题跟本题有什么关系呢？如果所有的
不如先形式化一下问题，现在有
这看似是一个非常复杂的问题，因为不清楚每个二元组中的
不如先对二元组进行一个排序，下面假设
- 先考虑一种简单的情况，若
f^{'}_k\ge \sum_{i=1}^{k-1} f^{'}_i + 2g^{'}_i ，那么显然最大的操作次数就是\sum_{i=1}^{k-1} f^{'}_i + 2g^{'}_i ，也就是g_u=(\sum_{i=1}^{k-1} f^{'}_i + 2g^{'}_i)+g^{'}_k ，f_u=k+f^{'}_k-(\sum_{i=1}^{k-1} f^{'}_i + 2g^{'}_i) 。
若
-
若
f^{'}_k< \sum_{i=1}^{k-1} f^{'}_i ，这个时候比较简单，不需要进行路径拆分，g_u=\lfloor\frac{\sum_{i=1}^k f^{'}_i}{2}\rfloor+\sum_{i=1}^k g^{'}_i ，f_u=k+((\sum_{i=1}^k f^{'}_i)\bmod 2) 。 -
若
f^{'}_k\ge \sum_{i=1}^{k-1} f^{'}_i ，这个时候需要进行路径拆分，由于保证了拆完路径后一定可以> f_k ，那么拆哪个子树的路径本质上是不重要的，甚至拆多少都是不重要的，只要满足拆完后和>f^{'}_k ，因为拆路径不会导致\sum_{i=1}^{k-1} f^{'}_i 的奇偶性发生改变！于是同样可以推出g_u=\lfloor\frac{\sum_{i=1}^k f^{'}_i}{2}\rfloor+\sum_{i=1}^k g^{'}_i ，f_u=k+((\sum_{i=1}^k f^{'}_i)\bmod 2) 。可以看出，这与上一种情况本质上是一样的。
那么至此就可以以
放个代码，由于作者写这题处于红温状态，图方便用了排序，复杂度带了 log，仅供参考。
#include <cstdio>
#include <map>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <random>
#include <cstring>
#include <ctime>
#include <cmath>
#include <assert.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define LL long long
#define pp pair<LL,LL>
#define mp make_pair
#define ull unsigned long long
namespace IO{
const int sz=1<<22;
char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
inline char gc(){
// return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
return getchar();
}
template<class T> void gi(T& x){
x=0; int f=1;char c=gc();
if(c=='-')f=-1;
for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc())
x=x*10+(c-'0');
x=x*f;
}
inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
template<class T> void pi(T x,char c='\n'){
if(x<0)pc('-'),x=-x;
if(x==0) pc('0'); int t=0;
for(;x;x/=10) p[++t]=x%10+'0';
for(;t;--t) pc(p[t]); pc(c);
}
struct F{~F(){flush();}}f;
}
using IO::gi;
using IO::pi;
using IO::pc;
const int mod=998244353;
inline int add(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
inline int dec(int x,int y){
return x-y<0?x-y+mod:x-y;
}
inline int mul(int x,int y){
return 1ll*x*y%mod;
}
inline int qkpow(int a,int b){
if(b<0)return 0;
int ans=1,base=a%mod;
while(b){
if(b&1)ans=1ll*ans*base%mod;
base=1ll*base*base%mod;
b>>=1;
}
return ans;
}
int fac[2000005],inv[2000005],Invn[600005];
inline int binom(int n,int m){
if(n<m||m<0)return 0;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void init_C(int n){
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[0]=1;
inv[n]=qkpow(fac[n],mod-2);
for(int i=n-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
// Invn[0]=Invn[1]=1;
// for(int i=1;i<=200000;i++)Invn[i]=(LL)(mod-mod/i)*Invn[mod%i]%mod;
}
int t,n,rt;
LL res,f[500005],g[500005];//f:up g:bouns
vector<int>G[500005];
vector<pp>buc[500005],Q[500005];
inline bool cmp(pp A,pp B){
return A.first<B.first;
}
inline void dfs(int u,int ff){
int son=0;
for(auto v:G[u]){
if(v==ff)continue;
son++;
dfs(v,u);
buc[u].push_back(pp(f[v],g[v]));
}
if(!son)return ;
res-=1ll*son*(son-1)/2;
if(u==rt)son--;
for(auto x:buc[u]){
LL v1=x.first,v2=x.second;
if(v1<=son){
LL need=son-v1;
if(2*v2>=need){
if(need&1){
v2-=(need+1)/2;
res+=(need+1)/2;
//up-->1 bouns--> v2
Q[u].push_back(pp(1,v2));
}else{
v2-=need/2;
res+=need/2;
//up-->0 bouns--> v2
Q[u].push_back(pp(0,v2));
}
}else{
//0 0
res+=v2;
res+=son-v1-v2*2;
}
}else{
v1-=son;
Q[u].push_back(pp(v1,v2));
}
}
f[u]=son;g[u]=0;
sort(Q[u].begin(),Q[u].end(),cmp);
if(Q[u].size()){
LL mx=0,sum=0;
for(auto x:Q[u])mx=max(mx,x.first);
LL sum2=0;
for(int i=0;i<Q[u].size()-1;i++){
pp x=Q[u][i];
res+=x.second;
sum2+=x.first+2*x.second;
}
if(sum2>=mx){
f[u]+=(sum2+mx)%2;
res-=(sum2+mx)/2;
g[u]+=(sum2+mx)/2+Q[u][Q[u].size()-1].second;
}else{
f[u]+=mx-sum2;
res-=sum2;
g[u]+=sum2+Q[u][Q[u].size()-1].second;
}
}
}
inline void solve(){
gi(n);
for(int i=1;i<=n;i++)G[i].clear(),buc[i].clear(),Q[i].clear(),f[i]=g[i]=0;
for(int i=1;i<n;i++){
int u,v;
gi(u),gi(v);
G[u].push_back(v);
G[v].push_back(u);
}
rt=0;
for(int i=1;i<=n;i++)if(G[i].size()==1)rt=i;
res=0;dfs(rt,0);
pi(res);
}
signed main(){
srand(time(0));
gi(t);
while(t--)solve();
return 0;
}