真真正正的淀粉质模板题。
为什么？之前那个O(N^2)检验子树的算法对于菊花图就很呵呵。
这个题，难点在于对子树的统计。
我们无法使用容斥一类的思想。
但是我们可以使用一种其他的方法。
也就是利用其中一颗的子树与其他子树的信息进行统计答案。
这样的话，就可以保证同一个子树内的信息不会被统计多次。
桶
#include#include #include #include /*using std::min;using std::max;*/const int N=201000;const int K=1010000;const int inf=0x7ffffff;struct node{ int p; int value; int nxt;};node line[N<<1];int head[N],tail;int size[N],f[N],vis[N];int root,sum,ans;int T[K];int n,k;int max(int a,int b){ return a > b ? a : b ;}int min(int a,int b){ return a < b ? a : b ;}int read(){ int res=0,flag=1; char c=getchar(); while(c>'9'||c<'0') { if(c=='-') flag=-1; c=getchar(); } while(c>='0'&&c<='9') { res=(res<<1)+(res<<3)+c-'0'; c=getchar(); } return res*flag;}void add(int a,int b,int c){ line[++tail].p=b; line[tail].value=c; line[tail].nxt=head[a]; head[a]=tail; return ;}void get_hry(int now,int fa){ size[now]=1;f[now]=0; int v; for(int i=head[now];i;i=line[i].nxt) { v=line[i].p; if(vis[v]||v==fa) continue; get_hry(v,now); f[now]=max(f[now],size[v]); size[now]+=size[v]; } f[now]=max(f[now],sum-size[now]); if(f[root]>f[now]) root=now; return ;}void get_DD(int now,int fa,int Dis,int Dep){ if(Dis>k) return ; ans=min(ans,T[k-Dis]+Dep); int v; for(int i=head[now];i;i=line[i].nxt) { v=line[i].p; if(v==fa||vis[v]) continue; get_DD(v,now,Dis+line[i].value,Dep+1); } return ;}void updata(int now,int fa,int Dis,int Dep,int model){ if(Dis>k) return ; if(model) T[Dis]=min(T[Dis],Dep); else T[Dis]=inf; int v; for(int i=head[now];i;i=line[i].nxt) { v=line[i].p; if(v==fa||vis[v]) continue; updata(v,now,Dis+line[i].value,Dep+1,model); } return ;}void solve(int now){ vis[now]=1; T[0]=0; int v; for(int i=head[now];i;i=line[i].nxt) { v=line[i].p; if(vis[v]) continue; get_DD(v,now,line[i].value,1); //ADD(); updata(v,now,line[i].value,1,1);; } for(int i=head[now];i;i=line[i].nxt) { v=line[i].p; if(vis[v]) continue; updata(v,now,line[i].value,1,0); } for(int i=head[now];i;i=line[i].nxt) { v=line[i].p; if(vis[v]) continue; sum=size[v];root=0; get_hry(v,now); solve(root); } return ;}int main(){ //scanf("%d%d",&n,&k); n=read(),k=read(); for(int i=1;i<=k;i++) T[i]=inf; for(int i=1,a,b,c;i