树形DP


  说是树形DP,其实就是求树的最长链嘛……

  K=1的时候明显是将树的最长链的两端连起来最优。

  但是K=2的时候怎么搞?

  考虑第一次找完树的最长链以后的影响:第一次找过的边如果第二次再走,对答案的贡献会变成-1,因为两次都选这一段的话,反而会使得这一段不得不走两次(如果只被选一次的话就可以只走一次),所以就将第一次找出的树的最长链上的边权值都改为-1。这个操作可以用链表实现(类比一下最小费用最大流的spfa实现!)

  题解:http://blog.csdn.net/qpswwww/article/details/43935861

 /**************************************************************
Problem: 1912
User: Tunix
Language: C++
Result: Accepted
Time:580 ms
Memory:5752 kb
****************************************************************/ //BZOJ 1912
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e5+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int head[N],to[N<<],next[N<<],len[N<<],cnt=;
void add(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; len[cnt]=;
to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt; len[cnt]=;
}
int n,K;
int D,S,son1[N],son2[N];
int dfs(int x,int fa){
int m1=,m2=;
for(int i=head[x];i;i=next[i])
if (to[i]!=fa){
int nowh=dfs(to[i],x)+len[i];
if (nowh>m1){m2=m1;m1=nowh;son2[x]=son1[x];son1[x]=i;}
else if (nowh>m2){m2=nowh; son2[x]=i;}
}
if (D<m1+m2) D=m1+m2,S=x;
return m1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1912.in","r",stdin);
freopen("1912.out","w",stdout);
#endif
n=getint(); K=getint();
F(i,,n){
int x=getint(),y=getint();
add(x,y);
}
int ans=(n-)<<;
D=;
CC(son1,-);
CC(son2,-);
dfs(,-);
ans-=D-;
if (K>){
D=;
for(int i=son1[S];i!=-;i=son1[to[i]]) len[i]=len[i^]=-;
for(int i=son2[S];i!=-;i=son1[to[i]]) len[i]=len[i^]=-;
CC(son1,-);
CC(son2,-);
dfs(,-);
ans-=D-;
}
printf("%d\n",ans);
return ;
}

1912: [Apio2010]patrol 巡逻

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 642  Solved: 362
[Submit][Status][Discuss]

Description

【BZOJ】【1912】【APIO2010】patrol巡逻-LMLPHP

Input

第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行,每行两个整数 a, b,
表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。

Output

输出一个整数,表示新建了K 条道路后能达到的最小巡逻距离。

Sample Input

8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6

Sample Output

11

HINT

10%的数据中,n ≤ 1000, K = 1;
30%的数据中,K = 1;
80%的数据中,每个村庄相邻的村庄数不超过 25;
90%的数据中,每个村庄相邻的村庄数不超过 150;
100%的数据中,3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

Source

[Submit][Status][Discuss]

04-29 01:13