這個題還是比較有趣的。。窩想的是dp。。
維護目前子樹已經是若幹條完整的鍊和有一條半鍊的情況，這其實和樹的直徑的合并就很像了。。。
然後還有這題還有貪心做法。。就是讓能成為拐點的點盡量成為拐點。。仔細想想可以發現，将2條鍊合并成一條鍊可以讓路徑數減一，除此以外的操作都會讓路徑數增加，是以如果能成為拐點，何樂而不為。。
最後貪心比dp跑得慢。。。
dp
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神獸保佑,代碼無bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1LL<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid ((x+y)/2)
#define NM 10005
#define nm 20005
#define pi 3.1415926535897931
const int inf=1e9+7;
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct edge{int t;edge*next;}e[nm],*h[NM],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
int n,d[NM][2],f[NM],_x,_y;
void dfs(int x){
link(x)if(j->t!=f[x]){
f[j->t]=x;
dfs(j->t);
d[x][0]+=d[j->t][0];
}
d[x][0]++;d[x][1]=d[x][0];
int _t=inf,__t=inf;
link(x)if(j->t!=f[x])
if(d[j->t][1]-d[j->t][0]<=_t)__t=_t,_t=d[j->t][1]-d[j->t][0];
else if(d[j->t][1]-d[j->t][0]<__t)__t=d[j->t][1]-d[j->t][0];
d[x][1]=min(d[x][1],d[x][1]-1+_t);
d[x][0]=min(d[x][0],d[x][0]-2+_t+__t);
d[x][0]=min(d[x][0],d[x][1]);
}
int main(){
int _=read();while(_--){
mem(d);mem(e);mem(h);o=e;mem(f);
n=read();inc(i,1,n-1){_x=read();_y=read();add(_x,_y);add(_y,_x);}
dfs(1);
printf("%d\n",min(d[1][1],d[1][0]));
}
return 0;
}
貪心
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神獸保佑,代碼無bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1LL<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid ((x+y)/2)
#define NM 10005
#define nm 20005
#define pi 3.1415926535897931
const int inf=1e9+7;
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct edge{int t;edge*next;}e[nm],*h[NM],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
int n,_x,_y,b[NM],f[NM],ans;
bool v[NM];
void dfs(int x){
link(x)if(j->t!=f[x]){
f[j->t]=x;
dfs(j->t);
}
int k=0,d=0;
link(x)if(j->t!=f[x]&&!v[j->t])if(!k)k=j->t;else d=j->t;
if(k&&d)ans--,v[x]++;
if(!k&&!d)ans++;
}
int main(){
int _=read();while(_--){
mem(e);mem(h);o=e;mem(v);mem(b);mem(f);
n=read();inc(i,1,n-1){_x=read();_y=read();add(_x,_y);add(_y,_x);b[_x]++;b[_y]++;}
mem(v);ans=0;_x=1;
inc(i,1,n)if(b[_x]<b[i])_x=i;
dfs(_x);
printf("%d\n",ans);
}
return 0;
}
1907: 樹的路徑覆寫
Time Limit: 5 Sec Memory Limit: 259 MB
Submit: 917 Solved: 433
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1
7
1 2
2 3
2 4
4 6
5 6
6 7
Sample Output
3
HINT
，注意此注釋有誤，第二種情況應該為{1,2,4,5,6},{3},{7}
Source
Play with Tree By Amber
[Submit][Status][Discuss]