2019MultiUniversityTrainingContest31011Squrirrel——树形DP

This way

题意&＃xff1a;

给你一棵树&＃xff0c;路径上都有权值&＃xff0c;你现在能将一条边权变为0&＃xff0c;问你从某个节点出发到最远的叶子结点的路径最短是多少。

题解:

这道题乍一看不难&＃xff0c;但是它的情况很多&＃xff0c;所以debug了很久才过。首先我们处理出每个节点距离它子树的叶子结点的最远&＃xff0c;第二远&＃xff0c;第三远的距离&＃xff0c;再用DP做出每个节点删掉一条边后到叶子结点最远&＃xff0c;第二远的距离。之后再用一个dfs做答案&＃xff0c;首先参数需要传&＃xff1a;
1.从父亲传下来的&＃xff0c;不包括这颗子树的最远未删边距离&＃xff0c;2.从父亲传下来的&＃xff0c;不包括这颗子树的最优最远删边距离。
那么这个节点的答案就是
min{max{父亲未删边,这棵树删边最大&＃xff0c;这棵树未删边第二大},max{父亲删边最优最大&＃xff0c;这棵树未删边最大}}
为什么&＃xff0c;因为不确定删边最大和未删边第二大的关系&＃xff0c;所以需要判一下。
先说一下重要数组的意义&＃xff1a;
no_mx&＃xff1a;表示未删边最大
no_smx&＃xff1a;表示未删边第二大
del_mx&＃xff1a;表示删边最大
no_&＃xff1a;表示父亲传下来的未删边最大
del_&＃xff1a;表示父亲传下来的删边最大
那么之后麻烦的就来了&＃xff0c;首先对于他的某一个儿子节点&＃xff0c;
1.如果他是这个点的未删边最大的儿子节点&＃xff1a;
1.1如果他是这个点的删边最大儿子节点&＃xff1a;
1.1.1他就会有no_smx,no_tmx,del_smx,del_tmx四种可以传下去的&＃xff0c;那么我们肯定是删掉no_smx,那么也就是说在no_tmx和del_smx中选择最大的
1.2如果他是这个点的第二或者其它儿子节点&＃xff1a;
1.2.1他就会有no_smx,no_tmx,del_mx,del_tmx四种可以传下去的&＃xff0c;那么我们不知道删掉no_smx还是del_mx&＃xff0c;那么我们就在这两个中取一个最小的&＃xff0c;在之后与no_tmx取个最大的
2.如果他是这个节点的未删边第二&＃xff1a;
2.1如果它是这个点的删边最大儿子节点&＃xff1a;
2.1.1他就会有no_mx,no_tmx,del_mx,del_tmx&＃xff0c;那么我们肯定是删掉no_mx&＃xff0c;所以在del_smx与no_tmx中取个最大的
2.2如果它是这个节点的删边第二大儿子节点或者其它&＃xff1a;
2.2.1它就会有no_mx,no_tmx,del_mx,del_tmx四种&＃xff0c;那么我们删掉no_mx&＃xff0c;所以在del_mx,与no_tmx中取个最大的
3.如果它是这个节点的未删边第三或者其它节点&＃xff1a;
3.1如果它是这个点的删边最大儿子节点&＃xff1a;
3.1.1它就会有no_mx&＃xff0c;no_smx,del_smx,del_tmx四种&＃xff0c;那么我们删掉no_mx,在no_smx,del_smx中取最大的
3.2如果它是这个点的删边第二或者其它儿子节点&＃xff1a;
3.2.1它就会有no_mx,no_smx,del_mx,del_tmx四种&＃xff0c;那么我们删掉no_mx,在no_smx,del_mx中取最大的

情况数有点多&＃xff0c;令人绝望的代码。

#include
using namespace std;
const int N&＃61;2e6&＃43;5;
int dp[N][2],no_mx[N],no_smx[N],no_tmx[N],del_mx[N],del_smx[N],del_tmx[N],ans[N];
struct node
{int to,next,w;
}e[N*2];
int cnt,head[N];
void add(int x,int y,int w)
{e[cnt].to&＃61;y;e[cnt].next&＃61;head[x];e[cnt].w&＃61;w;head[x]&＃61;cnt&＃43;&＃43;;
}
void dfs(int x,int fa)
{for(int i&＃61;head[x];~i;i&＃61;e[i].next){int ne&＃61;e[i].to,w&＃61;e[i].w;if(ne&＃61;&＃61;fa)continue;dfs(ne,x);if(no_mx[ne]&＃43;w>no_mx[x])no_tmx[x]&＃61;no_smx[x],no_smx[x]&＃61;no_mx[x],no_mx[x]&＃61;no_mx[ne]&＃43;w;else if(no_mx[ne]&＃43;w>no_smx[x])no_tmx[x]&＃61;no_smx[x],no_smx[x]&＃61;no_mx[ne]&＃43;w;else if(no_mx[ne]&＃43;w>no_tmx[x])no_tmx[x]&＃61;no_mx[ne]&＃43;w;int d&＃61;min(dp[ne][1]&＃43;w,dp[ne][0]);dp[x][1]&＃61;min(max(dp[x][0],d),max(dp[x][1],dp[ne][0]&＃43;w));dp[x][0]&＃61;max(dp[x][0],dp[ne][0]&＃43;w);if(d>del_mx[x])del_tmx[x]&＃61;del_smx[x],del_smx[x]&＃61;del_mx[x],del_mx[x]&＃61;d;else if(d>del_smx[x])del_tmx[x]&＃61;del_smx[x],del_smx[x]&＃61;d;else if(d>del_tmx[x])del_tmx[x]&＃61;d;}
}
int p,val;
void fans(int x,int fa,int no_,int del_)
{ans[x]&＃61;min(max(no_,max(del_mx[x],no_smx[x])),max(del_,no_mx[x]));if(ans[x]x)p&＃61;x;for(int i&＃61;head[x];~i;i&＃61;e[i].next){int ne&＃61;e[i].to,w&＃61;e[i].w;if(ne&＃61;&＃61;fa)continue;int nv&＃61;no_&＃43;w,nd;if(no_mx[ne]&＃43;w&＃61;&＃61;no_mx[x]){nv&＃61;max(nv,no_smx[x]&＃43;w);nd&＃61;min(max(no_,no_smx[x]),max(del_&＃43;w,no_smx[x]&＃43;w));//去掉这条边&＃xff0c;父亲传来的值if(min(dp[ne][1]&＃43;w,dp[ne][0])&＃61;&＃61;del_mx[x])nd&＃61;min(nd,max(del_smx[x]&＃43;w,max(no_&＃43;w,no_tmx[x]&＃43;w)));//去掉其它儿子边elsend&＃61;min(nd,max(no_&＃43;w,max(no_tmx[x]&＃43;w,min(del_mx[x]&＃43;w,no_smx[x]&＃43;w))));}else if(no_mx[ne]&＃43;w&＃61;&＃61;no_smx[x]){nv&＃61;max(nv,no_mx[x]&＃43;w);nd&＃61;min(max(no_,no_mx[x]),max(del_&＃43;w,no_mx[x]&＃43;w));if(min(dp[ne][1]&＃43;w,dp[ne][0])&＃61;&＃61;del_mx[x])nd&＃61;min(nd,max(del_smx[x]&＃43;w,max(no_&＃43;w,no_tmx[x]&＃43;w)));elsend&＃61;min(nd,max(no_&＃43;w,max(no_tmx[x]&＃43;w,del_mx[x]&＃43;w)));}else{nv&＃61;max(nv,no_mx[x]&＃43;w);nd&＃61;min(max(no_,no_mx[x]),max(del_&＃43;w,no_mx[x]&＃43;w));if(min(dp[ne][1]&＃43;w,dp[ne][0])&＃61;&＃61;del_mx[x])nd&＃61;min(nd,max(no_&＃43;w,max(no_smx[x]&＃43;w,del_smx[x]&＃43;w)));elsend&＃61;min(nd,max(no_&＃43;w,max(no_smx[x]&＃43;w,del_mx[x]&＃43;w)));}fans(ne,x,nv,nd);}
}
int main()
{//freopen("1.in","r",stdin);//freopen("out.txt","w",stdout);int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);memset(head,-1,sizeof(head));cnt&＃61;0;val&＃61;1e9;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)dp[i][0]&＃61;dp[i][1]&＃61;no_mx[i]&＃61;no_smx[i]&＃61;no_tmx[i]&＃61;del_mx[i]&＃61;del_smx[i]&＃61;del_tmx[i]&＃61;ans[i]&＃61;0;int x,y,w;for(int i&＃61;1;i}
/*
1
5
1 2 1
2 3 1
3 4 5
3 5 11
5
1 5 1
1 2 1
2 3 2
3 4 11
10
2 1 155
3 1 29
4 2 33
5 2 178
6 3 42
7 2 56
8 6 189
9 4 99
10 5 63
*/