Question link
CF direction
Luogu direction
Question solution
All along the path
0
0
0 would make the answer
?
1
-1
?1, all
1
1
1 will make the answer
?
2
-2
?2
Consider estimating the lower bound of the answer. An excellent solution is black and white dyeing
Then the lower bound of the answer that can be obtained at this time is
n
(
n
+
1
)
?
2
n
n(n + 1)-2n
n(n + 1)?2n
Then we can consider violence
d
p
dp
dp up
make
f
i
,
j
,
0
/
1
f_{i,j,0/1}
fi,j,0/1? for in
i
i
In the subtree of i,
i
i
The size of the connected block where i is located is
j
j
j, the color is
0
/
1
0/1
0/1 number of solutions
consider
j
j
The value range of j, because we get the lower bound of the answer, we can know
j
≤
n
j\le \sqrt n
j≤n
d
p
dp
dp is enough
time complexity
O
(
T
n
n
)
O(Tn\sqrt n)
O(Tnn
v
e
c
t
o
r
vector
vector stores arrays and releases them in time
#include <bits/stdc + + .h>
#define pb push_back
#define int long long
using namespace std;
const int N=200100,inf=1e18;
int n,B,siz[N];
int e[N<<1],ne[N<<1],h[N],idx;
vector<int> f[N][2];
inline int read(){<!-- -->
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1) + (FF<<3) + ch-48;
return FF*RR;
}
inline void chkmin(int & amp;x,int y){<!-- --> if(y<x) x=y;}
void dfs(int u,int fa){<!-- -->
f[u][0].pb(inf),f[u][0].pb(1),f[u][1].pb(inf),f[u][1].pb(2 );
siz[u]=1;
for(int i=h[u];~i;i=ne[i]){<!-- -->
int v=e[i];if(v==fa) continue;
dfs(v,u);
int LIM=min(siz[u] + siz[v],B) + 5;
vector<int> t[2];t[0].resize(LIM,inf),t[1].resize(LIM,inf);
for(int j=1;j<=min(siz[u],B);j + + ) for(int k=1;k<=min(siz[v],B);k + + ){< !-- -->
chkmin(t[0][j],f[u][0][j] + f[v][1][k]);
chkmin(t[1][j],f[u][1][j] + f[v][0][k]);
if(j + k<=B){<!-- -->
chkmin(t[0][j + k],f[u][0][j] + f[v][0][k] + j*k);
chkmin(t[1][j + k],f[u][1][j] + f[v][1][k] + j*k*2);
}
}
siz[u] + =siz[v];
f[u][0].resize(LIM);f[u][1].resize(LIM);
for(int j=0;j<LIM;j + + ) f[u][0][j]=t[0][j],f[u][1][j]=t[1][ j];
t[0].clear(),t[0].shrink_to_fit();
t[1].clear(),t[1].shrink_to_fit();
f[v][0].clear(),f[v][0].shrink_to_fit();
f[v][1].clear(),f[v][1].shrink_to_fit();
}
}
void add(int x,int y){<!-- --> e[idx]=y,ne[idx]=h[x],h[x]=idx + + ;}
void work(){<!-- -->
int n=read();
for(int i=1;i<=n;i + + ) h[i]=-1;idx=0;
for(int i=1;i<n;i + + ){<!-- -->
int x=read(),y=read();
add(x,y),add(y,x);
}
B=sqrt(n) + 5;
dfs(1,-1);
int res=inf;
for(int i=1;i<=min(siz[1],B);i + + ) res=min(res,min(f[1][0][i],f[1][1] [i]));
f[1][0].clear(),f[1][0].shrink_to_fit();
f[1][1].clear(),f[1][1].shrink_to_fit();
printf("%lld\\
",n*(n + 1)-res);
}
signed main(){<!-- -->
int T=read();
while(T--) work();
fprintf(stderr,"%d ms\\
",int64_t(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}