题目传送门

【题目大意】

【思路分析】

好的这道题目我在换根DP的部分卡了一个世纪……所以设状态真的很重要,我因为状态设的不好,然后换根的时候就很复杂QAQ

我来讲一下一个学长的做法叭QwQ

最后的连接情况是一棵树,首先我们要发现两个性质,就是在树中蓝线一定是连接在父子之间,并且连续的一段蓝线一定为偶数。

因为蓝线是删除了一条红线之后加入的,所以不可能存在类似下左图这种形状的连接方式,下右图这种连接方式才是合法的

然后因为每次添加两根蓝线(我们称这两根蓝线为一组),所以显然连续的蓝线数量必须是偶数。

总体思路是设1为根先DP一遍,然后换根,重要的是如何设状态可以在换根的时候方便转移。

我们设$f[x]$表示以$x$为根的子树的最大分数,注意此时这个子树可以单独出来,即子树中的蓝线数量为偶数。

$d[x][0]$结构体记录与$x$相连的,以$x$为根的子树中的边中最大的边的值和这条边连接的$x$的儿子,$d[x][1]$记录次大值及对应的儿子。当然记录的值保证更优,即记录下的儿子$y$在下左图的连接方式比下右图的连接方式更优。

转移见代码及注释

【代码实现】

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #define g() getchar()
 8 #define rg register
 9 #define go(i,a,b) for(rg int i=a;i<=b;i++)
10 #define back(i,a,b) for(rg int i=a;i>=b;i--)
11 #define db double
12 #define ll long long
13 #define il inline
14 #define pf printf
15 #define mem(a,b) memset(a,b,sizeof(a))
16 #define E(i,x) for(rg int i=hd[x];i;i=e[i].nxt)
17 #define t(i) e[i].to
18 #define w(i) e[i].w
19 using namespace std;
20 int fr(){
21     int w=0,q=1;
22     char ch=g();
23     while(ch<'0'||ch>'9'){
24         if(ch=='-') q=-1;
25         ch=g();
26     }
27     while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g();
28     return w*q;
29 }
30 const int N=200002;
31 const int INF=1e9+7;
32 int n,ed,hd[N],f[N],ans;
33 struct edge{
34     int nxt,to,w;
35 }e[N<<1];
36 struct node{
37     int frm,v;
38 }d[N][2];
39 il void build(rg int u,rg int v,rg int w){
40     e[++ed]=(edge){hd[u],v,w};hd[u]=ed;
41     swap(u,v);
42     e[++ed]=(edge){hd[u],v,w};hd[u]=ed;
43     return;
44 }
45 il void update(rg int x,rg int y,rg int w){
46     if(w>=d[x][0].v) d[x][1]=d[x][0],d[x][0]=(node){y,w};
47     else if(w>d[x][1].v) d[x][1]=(node){y,w};
48     return;
49 }
50 il void dp(rg int x,rg int fa){
51     d[x][0].v=d[x][1].v=-INF;f[x]=0;
52     E(i,x){
53         if(t(i)==fa) continue;
54         dp(t(i),x);
55         rg int as=max(f[t(i)],f[t(i)]+d[t(i)][0].v+w(i));//选择更优的连接方式
56         f[x]+=as;update(x,t(i),f[t(i)]+w(i)-as);
57         //这里的update有一个很巧妙的转化来判断那种连接方式更优
58     }    return;
59 }
60 il void dfs(rg int x,rg int fa){
61     ans=max(ans,f[x]);
62     E(i,x){
63         if(t(i)==fa) continue;
64         node d0=d[t(i)][0],d1=d[t(i)][1];//记录原来的值
65         rg int t1=f[t(i)],t2=max(t1,t1+d[t(i)][0].v+w(i));//找原来是怎么连接的
66         rg int f1=f[x]-t2,f2=(d[x][0].frm==t(i));//特判一下特殊情况
67         rg int as=max(f1,f1+d[x][f2].v+w(i));//把原本的父亲变为儿子连上去
68         f[t(i)]+=as;update(t(i),x,f1+w(i)-as);//更新d数组的值
69         dfs(t(i),x);
70         f[t(i)]=t1;d[t(i)][0]=d0;d[t(i)][1]=d1;//还原原来的值
71     }
72     return;
73 }
74 int main(){
75     //freopen("1.in","r",stdin);
76     //freopen("1.out","w",stdout);
77     n=fr();
78     go(i,1,n-1){
79         rg int u=fr(),v=fr(),w=fr();
80         build(u,v,w);
81     }
82     dp(1,0);ans=-INF;dfs(1,0);
83     pf("%d\n",ans);
84     return 0;
85 }
代码戳这里
02-14 02:05