P3047 [USACO12FEB]Nearby Cows G
题意:
给你一棵 \(n\) 个点的树,点带权,对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。
\(1\le n\le 1e5,1\le k\le 20 ,0\le c_i \le 1e3\)
解题思路:
一眼换根 \(\operatorname{dp}\)。问题是该如何设状态。
考虑设 \(f_{u,j}\) 为所有距离 \(u\) 节点 \(j\) 长度的权值和,对于第一次 \(\operatorname{dfs}\),显然应该如下转移:
\[f_{u,j}=\sum_{v\in son_u}f_{v,j-1} \](子树中距离 \(v\) 节点 \(j-1\) 长度的点即为距离 \(u\) 节点 \(j\) 长度的点)
对于第二次 \(\operatorname{dfs}\),我们已经知道了对于每个节点子树中的贡献,接下来应该计算子树之外的贡献。因此对于节点 \(u\),应该将子树中包含 \(v\) 节点的贡献减去,然后再让 \(v\) 节点加上此时 \(u\) 的其他子树和父亲的贡献,得到的就是最终答案。注意这某一子树搜索完之后要将 \(f_u\) 的状态恢复。
转移式为:
\[f_{u,j}=f_{u,j}-f_{v,j-1} \\ f_{v,j}=f_{v,j}+f_{u,j-1} \]对于每个节点 \(u\), 答案为 \(\sum_{j=0}^{k}f_{u,j}\)。
代码:
code
#include <cstdio>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=101000;
int n,K,cnt,head[maxn],a[maxn];
int dep[maxn],ans[maxn];
int f[maxn][30];
struct ED{
int nxt,to;
}e[maxn<<1];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inline void dfs(int u,int fa){
f[u][0]=a[u];
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
for(Reg int j=K;j>=1;j--) f[u][j]+=f[v][j-1];
}
}
inline void dfs_2(int u,int fa){
for(Reg int i=0;i<=K;++i) ans[u]+=f[u][i];
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
for(Reg int j=K;j>=1;j--) f[u][j]-=f[v][j-1];
for(Reg int j=K;j>=1;j--) f[v][j]+=f[u][j-1];
dfs_2(v,u);
for(Reg int j=K;j>=1;j--) f[v][j]-=f[u][j-1];
for(Reg int j=K;j>=1;j--) f[u][j]+=f[v][j-1];
}
}
int main(){
n=read(),K=read();
for(Reg int i=1;i<=n-1;++i){
int x=read(),y=read();
add(x,y),add(y,x);
}
for(Reg int i=1;i<=n;++i) a[i]=read();
dfs(1,0),dfs_2(1,0);
for(Reg int i=1;i<=n;++i) printf("%d\n",ans[i]);
return 0;
}
P1272 重建道路
题意:
给定一棵 \(n\) 个节点的树,询问使包含 \(P\) 个节点的连通块与这棵树分离所需要砍掉的最小边数。
$1\le n\le 150,1\le P\le n $
解题思路:
设计状态是关键...不然就会像某人一样死活调不出来,连自己假没假都不知道。
设 \(f_{u,t}\) 为在 \(u\) 节点的子树中砍掉 \(t\) 个节点所需砍掉的最小边数,易知当 \(u\) 不为根节点时 \(f_{u,siz_u}=1\),以及任意情况下都有 \(f_{u,0}=0\)。其他初始化为 \(inf\)。
接下来思考如何转移以及计算答案。
转移比较好说,是一般树形背包的套路,即:
\[f_{u,t}=\min(f_{u,t},f_{u,t-j}+f_{v,j}) \]计算答案则是:
\[ans=\min(ans,f_{u,siz_u-P}+f_{u,siz_u}) \](即砍掉子树中的一些点再分离出来整棵子树)
代码:
code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=210,inf=2147483100;
int n,K,cnt,ans=inf,siz[maxn],head[maxn];
int f[maxn][maxn];
struct ED{
int to,nxt;
}e[maxn<<1];
//定义状态很重要
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inline void dfso(int u){
siz[u]=1;
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
//printf("%d %d\n",u,v);
dfso(v);
siz[u]+=siz[v];
}
f[u][siz[u]]=1;
f[u][0]=0;
}
inline void dfst(int u){
// printf("%d\n",u);
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
//printf("%d %d\n",u,v);
dfst(v);
for(Reg int t=siz[u]-1;t;--t)
for(Reg int k=0;k<=t;++k)
f[u][t]=min(f[u][t],f[u][t-k]+f[v][k]);
}
if(siz[u]>=K) ans=min(ans,f[u][siz[u]-K]+f[u][siz[u]]);
}
int main(){
n=read(),K=read();
//printf("1\n");
for(Reg int i=1;i<n;++i){
int x=read(),y=read();
add(x,y);
}
//printf("1\n");
memset(f,0x3f,sizeof(f));
//memset(minn,0x3f,sizeof(minn));
dfso(1);
f[1][siz[1]]=0;
dfst(1);
printf("%d\n",ans);
return 0;
}
P3761 [TJOI2017]城市
题意:
给定一棵 \(n\) 个节点的树,边带权,可以断开一条边再在另外一个位置连上一条边权相同的边(依然要保证是棵树),求进行一次操作后两个节点最大距离的最小值。
$1\le n\le 5e3 $
解题思路:
盲猜有人想用二分
事实上二分根本不可写。
发现断开的这一条边一定会是直径上的边,否则距离最大的依然会是直径。
继续发现断开某一条边后树会分为两个连通块,再连边肯定是于两个联通块之间连边。
枚举直径上的一条边 \((u,v,w)\) ,考虑答案如何被更新:
-
\(u\) 所在连通块的两点之间最大距离。
-
\(v\) 所在连通块的两点之间最大距离。
-
块内所有点关于 \(x\) 的最大距离加上块内所有点关于 \(y\) 的最大距离加上 \(w\)。
(其中 \(x\) 属于 \(u\) 所在的连通块,\(y\) 属于 \(v\) 所在的连通块,枚举可得)
三者取 \(\max\) ,再对 \(ans\) 取 \(\min\) 即可。
好,发现可以无脑树剖搞了,这样的复杂度大概为 \(O(n^3 \log^2 n)\),可以拿到 \(\operatorname{30pts}\)。
能不能再给力一点儿?
好像意识到了什么。
\(u\) 所在连通块的两点之间最大距离。
\(v\) 所在连通块的两点之间最大距离。
显然是树的直径。
块内所有点关于 \(x\) 的最大距离加上块内所有点关于 \(y\) 的最大距离加上 \(w\)。
因为要使答案最小,而且两个连通块选什么点互不影响,我们分明可以选择对块内所有点最大距离最小的 \(x\) 和 \(y\) 。这需要知道每个 \(x\) 或者 \(y\) 对块内所有点的最大距离。
考虑换根 \(\operatorname{dp}\) 。
首先对每个连通块进行第一次 \(\operatorname{dfs}\) 以求出子树内叶节点与该节点的最大距离 \(f_{u,0}\) ,以及树的直径。
对于第二次 \(\operatorname{dfs}\),对于某个节点的贡献是子树以内的最长链或者是子树以外的最长链。 其中子树以内的最长链已经求出。设 \(d_u\) 为 \(u\) 节点子树以外的最长链,那么转移应该为:
\[d_v=\max(d_v,\max(d_u,f_{u,0})) \]但是当 \(v\) 本身属于最长链时上述方程不成立,因此还要在第一次的 \(\operatorname{dfs}\) 维护一个子树内次长链 \(f_{u,1}\) ,并记录最长链对应的节点 \(fir_u\)。最终的转移为:
\[d_v= \begin {cases} \max(d_v,\max(d_u,f_{u,0})) \ \ \ \ \ \ \ \ \ \ \ \ (v=fir_u) \\ \max(d_v,\max(d_u,f_{u,1})) \ \ \ \ \ \ \ \ \ \ \ \ (v\ne fir_u) \end{cases} \]取 $\min $ 可得合法的 \(x,y\) 。
设两个连通块直径取 \(\max\) 后的结果为 \(res\),那么答案为:
\[ans=\min(ans,\max(res,d_x+d_y+w)) \]代码:
code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=5005,inf=2147483100;
int n,cnt,lroot,rroot,maxx,ans;
int head[maxn],vis[maxn],dismax[maxn],dissec[maxn],fir[maxn],sec[maxn];
int evis[maxn],dis[maxn],pvis[maxn];
struct ED{
int to,nxt,w;
}e[maxn<<1];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void add(int u,int v,int w){
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inline void dfs(int u,int fa,int depth){
if(depth>maxx) ans=maxx=depth,rroot=u;
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u,depth+e[i].w);
}
}
int res=0,minu=inf,minv=inf;
inline void fdfs(int u,int fa){
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(evis[i+1>>1]) continue;
if(v==fa) continue;
fdfs(v,u);
res=max(res,dismax[u]+dismax[v]+w);
if(dismax[v]+w>dismax[u]){
dissec[u]=dismax[u];
sec[u]=fir[u];
dismax[u]=dismax[v]+w;
fir[u]=v;
}else if(dismax[v]+w>dissec[u]){
dissec[u]=dismax[v]+w;
sec[u]=v;
}
}
}
inline void pdfs(int u,int fa,int idx,int S){
if(!idx) minu=min(minu,max(dismax[u],S));
else minv=min(minv,max(dismax[u],S));
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(evis[i+1>>1]) continue;
if(v==fa) continue;
if(v==fir[u]){
if(sec[u])pdfs(v,u,idx,max(S,dissec[u])+e[i].w);
else pdfs(v,u,idx,S+e[i].w);
}
else pdfs(v,u,idx,max(S,dismax[u])+e[i].w);
}
}
inline void solve(int u,int v,int x){
res=0,minu=inf,minv=inf;
memset(fir,0,sizeof(int)*(n+10));
memset(sec,0,sizeof(int)*(n+10));
memset(dismax,0,sizeof(int)*(n+10));
memset(dissec,0,sizeof(int)*(n+10));
fdfs(u,0);pdfs(u,0,0,0);
fdfs(v,0);pdfs(v,0,1,0);
ans=min(ans,max(res,x+minu+minv));
}
inline void finds(int u,int fa){
if(u==rroot) vis[u]=1;
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
finds(v,u);
if(vis[v]){
evis[i+1>>1]=1;
solve(u,v,e[i].w);
vis[u]=1;
evis[i+1>>1]=0;
}
}
}
int main(){
n=read();
for(Reg int i=1;i<n;++i){
int x=read(),y=read(),w=read();
add(x,y,w),add(y,x,w);
}
dfs(1,0,0);lroot=rroot,maxx=0;
dfs(lroot,0,0);
//printf("%d %d\n",lroot,rroot);
finds(lroot,0);
printf("%d\n",ans);
return 0;
}
CF708C Centroids
题意:
给定一颗树,你有一次将树改造的机会,改造的意思是删去一条边,再加入一条边,保证改造后还是一棵树。
请问有多少点可以通过改造,成为这颗树的重心?(如果以某个点为根,每个子树的大小都不大于\(\lfloor \frac{n}{2} \rfloor\),则称某个点为重心)
\(n\le 4e5\)
解题思路:
一眼换根 \(\operatorname{dp}\)。
能推出来对于某个点若不满足重心的要求,可以将其一个大小大于 \(\lfloor \frac{n}{2} \rfloor\) 的子树切下一个最大的小于等于 \(\lfloor \frac{n}{2} \rfloor\) 的部分接到根上。
然后发现不会设状态,颓了眼题解,于是对 \(\operatorname{BE}\) 是神必这件事深以为然。
设 \(f_u\) 为子树内最大的小于等于 \(\lfloor \frac{n}{2} \rfloor\) 的部分,转移如下:
\[f_u= \begin {cases} \max(f_u,siz_v) \ \ \ \ \ \ \ \ \ (siz_v \le \lfloor \frac{n}{2} \rfloor) \\ \max(f_u,f_v) \ \ \ \ \ \ \ \ \ \ \ \ (siz_v > \lfloor \frac{n}{2} \rfloor) \end{cases} \](比较显然)
但是要求换根。
那么就需要跟上一道题一样,要维护最大值和次大值了(转移方程不写力)。
如果说这个节点本来就是重心那么它可以被改造成重心(废话),否则必须满足如下要求:
\[(maxsiz_u-f_u \le \lfloor \frac{n}{2} \rfloor) \]当然 \(maxsiz_u\) 可以是父节点的那一部分 ( \(n-siz_u\) )。
然后就做完了。
代码:
code
#include <cstdio>
#include <algorithm>
#define Reg register
using namespace std;
const int maxn=410000;
int n,cnt,head[maxn],siz[maxn],fir[maxn],sec[maxn],maxsiz[maxn];
int vis[maxn],f[maxn][2],dp[maxn];
struct ED{
int to,nxt;
}e[maxn<<1];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inline void dfso(int u,int fa){
siz[u]=1;
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfso(v,u);
maxsiz[u]=max(maxsiz[u],siz[v]);
if(siz[v]<=n/2){
if(siz[v]>f[u][0]){
f[u][1]=f[u][0],sec[u]=fir[u];
f[u][0]=siz[v],fir[u]=v;
}else if(siz[v]>f[u][1]){
f[u][1]=siz[v],sec[u]=v;
}
}else{
if(f[v][0]>f[u][0]){
f[u][1]=f[u][0],sec[u]=fir[u];
f[u][0]=f[v][0],fir[u]=v;
}else if(f[v][0]>f[u][1]){
f[u][1]=f[v][0],sec[u]=v;
}
}
siz[u]+=siz[v];
}
// printf("%d %d\n",f[u][0],f[u][1]);
}
inline void dfst(int u,int fa){
vis[u]=1;
if(maxsiz[u]>n/2) vis[u]=((maxsiz[u]-f[u][0])<=n/2);
else if(n-siz[u]>n/2) vis[u]=((n-siz[u]-dp[u])<=n/2);
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
if(n-siz[v]<=n/2) dp[v]=max(dp[v],n-siz[v]);
else dp[v]=max(dp[v],dp[u]);
if(v==fir[u]){
if(sec[u]) dp[v]=max(dp[v],f[u][1]);
dfst(v,u);
}else{
dp[v]=max(dp[v],f[u][0]);
dfst(v,u);
}
}
}
int main(){
n=read();
for(Reg int i=1;i<n;++i){
int x=read(),y=read();
add(x,y),add(y,x);
}
dfso(1,0),dfst(1,0);
for(Reg int i=1;i<=n;++i) printf("%d ",vis[i]);
printf("\n");
return 0;
}
累麻。
标签:有意思,le,int,max,树形,maxn,siz,节点,dp From: https://www.cnblogs.com/Broken-Eclipse/p/16874286.html