题目传送门
【题目大意】
【思路分析】
好的这道题目我在换根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 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11598904.html
