[八省联考2018]林克卡特树lct

题解:

zhcs的那个题基本上就是抄这个题的，不过背包的分数变成了70分。。

不过得分开来写。。因为两个数组不能同时满足

背包的话就是

$f[i][j][0/1]$表示考虑i子树，取j条链，能不能向上扩展的最大值

然后辅助数组$g[i][j][0/1/2/3]$表示考虑i子树，不取根，取根，取根连一条向下链，取根连两条向下链

然后代码非常好写（边界情况注意一下就可以了）

另外这个的时间复杂度$nk$分析是个比较套路的东西

我们转移的时候需要给j这一维$min$一个子树大小，不然就是$n*k^2$的了

由于看时间比较宽松。。我写的常数巨大。。感觉稍微卡卡可以快4-5倍

正解很简单，但是wqs二分用的不多应该不太会想到。。

因为感觉上这个是可以用其他来优化的

#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for(int i=h;i<=t;i++)
#define dep(i,t,h) for(int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define mep(x,y) memcpy(x,y,sizeof(y))
#define mid (t<=0?(h+t-1)/2:(h+t)/2)
namespace IO{
    char ss[1<<24],*A=ss,*B=ss;
    IL char gc()
    {
        return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
    }
    template<class T> void read(T &x)
    {
        rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);
        while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f; 
    }
    char sr[1<<24],z[20]; ll Z,C1=-1;
    template<class T>void wer(T x)
    {
        if (x<0) sr[++C1]='-',x=-x;
        while (z[++Z]=x%10+48,x/=10);
        while (sr[++C1]=z[Z],--Z);
    }
    IL void wer1()
    {
        sr[++C1]=' ';
    }
    IL void wer2()
    {
        sr[++C1]='
';
    }
    template<class T>IL void maxa(T &x,T y) {if (x<y) x=y;}
    template<class T>IL void mina(T &x,T y) {if (x>y) x=y;} 
    template<class T>IL T MAX(T x,T y){return x>y?x:y;}
    template<class T>IL T MIN(T x,T y){return x<y?x:y;}
};
using namespace IO;
const int N=1500;
const int N2=1.5e5;
const int INF=1e9;
struct re{
    int a,b,c;
}e[N2*2];
int l,head[N2];
int f[N][N][2],g[N][N][4],g1[N][4],num[N],n,m,k;
void arr(int x,int y,int z)
{
    e[++l].a=head[x];
    e[l].b=y;
    e[l].c=z;
    head[x]=l;
}
struct query2{
    int f[N2][4][2],g[N2][4][4],g1[4][4],num[N2];
    void dfs(int x,int y)
{
    num[x]=1;
    g[x][0][1]=g[x][0][2]=g[x][0][3]=-INF;
    for (rint u=head[x];u;u=e[u].a)
    {
        int v=e[u].b;
        if (v!=y)
        { 
          dfs(v,x);
          rep(i,0,MIN(k,num[x])) 
            g1[i][0]=g[x][i][0],g1[i][1]=g[x][i][1],g1[i][2]=g[x][i][2],g1[i][3]=g[x][i][3];
          dep(i,MIN(k,num[x]),0)
            dep(j,MIN(k,num[v]),0)
            if (i+j-1<=k)
            {
              maxa(g[x][i+j][0],g1[i][0]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][1],g1[i][1]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][2],g1[i][2]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][3],g1[i][3]+MAX(f[v][j][1],f[v][j][0])); 
              if (i>0&&j>0) maxa(g[x][i+j-1][3],g1[i][2]+f[v][j][1]+e[u].c);
              if (i>0&&j>0) maxa(g[x][i+j-1][2],g1[i][1]+f[v][j][1]+e[u].c);
            }
          num[x]+=num[v];
        }
    }
    rep(i,0,MIN(num[x],k)) 
      f[x][i][0]=MAX(g[x][i][0],g[x][i][3]),
      f[x][i][1]=MAX(g[x][i][1],g[x][i][2]);
}
}S;
void dfs(int x,int y)
{
    num[x]=1;
    g[x][0][1]=g[x][0][2]=g[x][0][3]=-INF;
    for (rint u=head[x];u;u=e[u].a)
    {
        int v=e[u].b;
        if (v!=y)
        { 
          dfs(v,x);
          rep(i,0,num[x]) 
            g1[i][0]=g[x][i][0],g1[i][1]=g[x][i][1],g1[i][2]=g[x][i][2],g1[i][3]=g[x][i][3];
          dep(i,MIN(k,num[x]),0)
            dep(j,MIN(k,num[v]),0)
            if (i+j-1<=k)
            {
              maxa(g[x][i+j][0],g1[i][0]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][1],g1[i][1]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][2],g1[i][2]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][3],g1[i][3]+MAX(f[v][j][1],f[v][j][0])); 
              if (i>0&&j>0) maxa(g[x][i+j-1][3],g1[i][2]+f[v][j][1]+e[u].c);
              if (i>0&&j>0) maxa(g[x][i+j-1][2],g1[i][1]+f[v][j][1]+e[u].c);
            }
          num[x]+=num[v];
        }
    }
    rep(i,0,MIN(num[x],k)) 
      f[x][i][0]=MAX(g[x][i][0],g[x][i][3]),
      f[x][i][1]=MAX(g[x][i][1],g[x][i][2]);
}
int main()
{
    read(n); read(k);
    rep(i,1,n-1)
    {
        int x,y,z;
        read(x); read(y); read(z);
        arr(x,y,z); arr(y,x,z);
    }
    if (k==1)
    {
        S.dfs(1,0);
        cout<<MAX(S.f[1][k][0],S.f[1][k][1])<<endl;
    } else
    {
      dfs(1,0);
      cout<<MAX(f[1][k][0],f[1][k][1])<<endl;
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for(int i=h;i<=t;i++)
#define dep(i,t,h) for(int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define mep(x,y) memcpy(x,y,sizeof(y))
#define mid (t<=0?(h+t-1)/2:(h+t)/2)
namespace IO{
    char ss[1<<24],*A=ss,*B=ss;
    IL char gc()
    {
        return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
    }
    template<class T> void read(T &x)
    {
        rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);
        while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f; 
    }
    char sr[1<<24],z[20]; ll Z,C1=-1;
    template<class T>void wer(T x)
    {
        if (x<0) sr[++C1]='-',x=-x;
        while (z[++Z]=x%10+48,x/=10);
        while (sr[++C1]=z[Z],--Z);
    }
    IL void wer1()
    {
        sr[++C1]=' ';
    }
    IL void wer2()
    {
        sr[++C1]='
';
    }
    template<class T>IL void maxa(T &x,T y) {if (x<y) x=y;}
    template<class T>IL void mina(T &x,T y) {if (x>y) x=y;} 
    template<class T>IL T MAX(T x,T y){return x>y?x:y;}
    template<class T>IL T MIN(T x,T y){return x<y?x:y;}
};
using namespace IO;
const int N=110;
const int N2=3.1e5;
const int INF=1e9;
struct re{
    int a,b,c;
}e[N2*2];
int l,head[N2];
int f[N2][N][2],g[N2][N][4],g1[N2][4],num[N2],n,m,k;
void arr(int x,int y,int z)
{
    e[++l].a=head[x];
    e[l].b=y;
    e[l].c=z;
    head[x]=l;
}
void dfs(int x,int y)
{
    num[x]=1;
    g[x][0][1]=g[x][0][2]=g[x][0][3]=-INF;
    for (rint u=head[x];u;u=e[u].a)
    {
        int v=e[u].b;
        if (v!=y)
        { 
          dfs(v,x);
          rep(i,0,MIN(k,num[x])) 
            g1[i][0]=g[x][i][0],g1[i][1]=g[x][i][1],g1[i][2]=g[x][i][2],g1[i][3]=g[x][i][3];
          dep(i,MIN(k,num[x]),0)
            dep(j,MIN(k,num[v]),0)
            if (i+j-1<=k)
            {
              maxa(g[x][i+j][0],g1[i][0]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][1],g1[i][1]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][2],g1[i][2]+MAX(f[v][j][1],f[v][j][0]));
              maxa(g[x][i+j][3],g1[i][3]+MAX(f[v][j][1],f[v][j][0])); 
              if (i>0&&j>0) maxa(g[x][i+j-1][3],g1[i][2]+f[v][j][1]+e[u].c);
              if (i>0&&j>0) maxa(g[x][i+j-1][2],g1[i][1]+f[v][j][1]+e[u].c);
            }
          num[x]+=num[v];
        }
    }
    rep(i,0,MIN(num[x],k)) 
      f[x][i][0]=MAX(g[x][i][0],g[x][i][3]),
      f[x][i][1]=MAX(g[x][i][1],g[x][i][2]);
}
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    read(n); read(k); k++;
    rep(i,1,n-1)
    {
        int x,y,z;
        read(x); read(y); read(z);
        arr(x,y,z); arr(y,x,z);
    }
    dfs(1,0);
    cout<<MAX(f[1][k][0],f[1][k][1])<<endl;
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yinwuxiao/p/10082118.html