Sample Input
2 3 2 1 2 3 2 5 5 2 1 7 3 1 7 4 2 5 5 2 6
Sample Output
7 63
这类题目就是分类讨论，需要多做做。
1 #include2 #include 3 #include 4 using namespace std; 5 const int N=100010; 6 int cnt,fir[N],nxt[N*2],to[N*2],val[N*2]; 7 void addedge(int a,int b,int v){ 8 nxt[++cnt]=fir[a]; 9 to[fir[a]=cnt]=b;10 val[cnt]=v;11 }12 int Mx[N],dp[N][3],pos[N][2];13 void Update(int x,int d,int t){14 if(d>dp[x][0]){dp[x][2]=dp[x][1];dp[x][1]=dp[x][0];pos[x][1]=pos[x][0];pos[x][0]=t;dp[x][0]=d;}15 else if(d>dp[x][1]){dp[x][2]=dp[x][1];pos[x][1]=t;dp[x][1]=d;}16 else if(d>dp[x][2])dp[x][2]=d;17 }18 void DFS(int x,int fa){19 for(int i=fir[x];i;i=nxt[i])20 if(to[i]!=fa){DFS(to[i],x);21 int d=dp[to[i]][0]+val[i];22 Mx[x]=max(Mx[x],Mx[to[i]]);23 Update(x,d,to[i]);24 }25 Mx[x]=max(Mx[x],dp[x][0]+dp[x][1]); 26 }27 28 int down[N],give[N];29 long long ans;30 void DP(int x,int fa){31 Update(x,give[x],0);//往回走的最长链32 int d1=0,d2=0,p,d;33 for(int i=fir[x];i;i=nxt[i])34 if(to[i]!=fa){35 if(Mx[to[i]]>d1)d2=d1,d1=Mx[to[i]],p=to[i];36 else if(Mx[to[i]]>d2)d2=Mx[to[i]];37 }38 for(int i=fir[x];i;i=nxt[i])39 if(to[i]!=fa){40 if(pos[x][0]==to[i])d=dp[x][1]+dp[x][2];41 else if(pos[x][1]==to[i])d=dp[x][0]+dp[x][2];42 else d=dp[x][0]+dp[x][1];43 44 if(to[i]!=p)d=max(d,d1);45 else d=max(d,d2);46 47 d=max(down[x],d);ans+=max(Mx[to[i]],d);down[to[i]]=d;48 if(pos[x][0]!=to[i])give[to[i]]=dp[x][0]+val[i];49 else give[to[i]]=dp[x][1]+val[i];50 DP(to[i],x);51 }52 }53 54 void Init(){55 memset(give,0,sizeof(give));56 memset(down,0,sizeof(down));57 memset(fir,0,sizeof(fir));58 memset(pos,0,sizeof(pos));59 memset(Mx,0,sizeof(Mx));60 memset(dp,0,sizeof(dp));61 ans=cnt=0;62 }63 int T,n;64 int main(){65 scanf("%d",&T);66 while(T--){67 Init();scanf("%d",&n);68 for(int i=1,a,b,v;i