[POJ&HDU]杂题记录

POJ2152

树形dp，每次先dfs一遍求出距离再枚举所有点转移即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 1010
int N,T,d[MAXN],c[MAXN];
struct EdgeNode{int next,to,dis;}edge[MAXN<<];
int head[MAXN],cnt=;
int f[MAXN][MAXN],g[MAXN],deep[MAXN];
inline void AddEdge(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; edge[cnt].to=v; edge[cnt].dis=w; head[u]=cnt;}
inline void InsertEdge(int u,int v,int w) {AddEdge(u,v,w); AddEdge(v,u,w);}
inline void DFS_1(int now,int last)
{
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            deep[edge[i].to]=deep[now]+edge[i].dis,
            DFS_1(edge[i].to,now);
}
inline void DFS_2(int now,int last)
{
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            DFS_2(edge[i].to,now);
    deep[now]=; DFS_1(now,);
    for (int j=; j<=N; j++)
        if (deep[j]<=d[now])
            {
                f[now][j]=c[j];
                for (int i=head[now]; i; i=edge[i].next)
                    if (edge[i].to!=last)
                        f[now][j]+=min(g[edge[i].to],f[edge[i].to][j]-c[j]);
                g[now]=min(g[now],f[now][j]);
            }
}
int main()
{
    T=read();
    while (T--)
        {
            N=read();
            for (int i=; i<=N; i++) c[i]=read();
            for (int i=; i<=N; i++) d[i]=read();
            cnt=; memset(head,,sizeof(head));
            for (int i=,x,y,z; i<=N-; i++) x=read(),y=read(),z=read(),InsertEdge(x,y,z);
            memset(f,,sizeof(f)); memset(g,,sizeof(g));
            DFS_2(,);
//            for (int i=1; i<=N; i++)
//                for (int j=1; j<=N; j++)
//                    printf("%d %d %d\n",i,j,f[i][j]);
            printf("%d\n",g[]);
        }
    return ;
}

POJ2152

POJ3280

区间dp，最小回文代价

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
#define MAXN 3010
int N,M,add[],del[],dp[MAXN][MAXN],hash[];
char s[MAXN],ss[][];
int main()
{
    scanf("%d%d%s",&N,&M,s+);
    for (int i=; i<=N; i++) scanf("%s%d%d",ss[i]+,&add[i],&del[i]),hash[ss[i][]-'a'+]=i;
//    memset(dp,63,sizeof(dp));
    for (int i=; i<=M; i++) dp[i][i]=;
    for (int len=; len<=M; len++)
        for (int l=,r=l+len-; l+len-<=M; l++,r++)
        {
            dp[l][r]=0x3f3f3f3f;
            if (s[l]==s[r])
                dp[l][r]=dp[l+][r-];
            else
                dp[l][r]=min(dp[l][r],dp[l+][r]+min(add[ hash[ s[l]-'a'+ ] ],del[ hash[ s[l]-'a'+ ] ])),
                dp[l][r]=min(dp[l][r],dp[l][r-]+min(add[ hash[ s[r]-'a'+ ] ],del[ hash[ s[r]-'a'+ ] ]));
//            printf("%d %d %d\n",l,r,dp[l][r]);
        }
    printf("%d\n",dp[][M]);
    return ;
}

POJ2152

POJ1988

带权并查集

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 300010
int N,f[MAXN],Q,h[MAXN],d[MAXN];
inline int F(int x)
{
    if (f[x]==x) return x;
    int fx=f[x];
    f[x]=F(f[x]); h[x]+=h[fx];
    return f[x];
}
inline void merge(int x,int y)
{
    int fx=F(x),fy=F(y);
    if (fx==fy) return;
    f[fx]=fy; h[fx]=d[fy]; d[fy]+=d[fx]; d[fx]=;
}
int main()
{
    Q=N=read();
    for (int i=; i<=; i++) f[i]=i,h[i]=,d[i]=;
    while (Q--)
        {
            char opt[]; scanf("%s",opt); int x,y;
            switch (opt[])
                {
                    case 'M': x=read(),y=read(),merge(x,y); break;
                    case 'C': x=read(); y=F(x); printf("%d\n",h[x]); break;
                }
        }
    return ;
}

POJ1988

POJ1984

带权并查集，把四个方向的运算换成向量运算即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 100010
int N,M,Q,ans[MAXN];
struct QNode{int u,v,t,id;}q[MAXN];
struct ENode{int u,v,dis,dir[];}e[MAXN];
struct Vector
{
    int x,y;
    inline int Len() {return abs(x)+abs(y);}
}V[MAXN];
Vector operator + (Vector A,Vector B) {return (Vector){A.x+B.x,A.y+B.y};}
Vector operator - (Vector A,Vector B) {return (Vector){A.x-B.x,A.y-B.y};}
inline bool cmp(QNode A,QNode B) {return A.t<B.t;}
int f[MAXN];
inline int F(int x) {if (f[x]==x) return x; int y=f[x]; f[x]=F(f[x]); V[x]=V[x]+V[y]; return f[x];}

inline void merge(int x,int y,Vector v)
{
    int fx=F(x),fy=F(y);
    if (fx==fy) return;
    f[fy]=fx;
    V[fy]=V[x]-V[y]+v;
}
inline void Merge(ENode edge)
{
    int x=edge.u,y=edge.v,d=edge.dis; char dir=edge.dir[];
    switch(dir)
        {
            case 'N': merge(x,y,(Vector){,d}); break;
            case 'E': merge(x,y,(Vector){d,}); break;
            case 'S': merge(x,y,(Vector){,-d}); break;
            case 'W': merge(x,y,(Vector){-d,}); break;
        }
}
int main()
{
    N=read(); M=read();
    for (int i=; i<=M; i++)
        e[i].u=read(),e[i].v=read(),e[i].dis=read(),scanf("%s",e[i].dir);
    Q=read();
    for (int i=; i<=Q; i++) q[i].u=read(),q[i].v=read(),q[i].t=read(),q[i].id=i;
    sort(q+,q+Q+,cmp);
    for (int i=; i<=N; i++) f[i]=i;
    for (int i=,j=; i<=Q; i++)
        {
            while (j<=q[i].t && j<=M) Merge(e[j++]);
            int fx=F(q[i].u),fy=F(q[i].v);
            ans[q[i].id]=fx==fy? (V[q[i].u]-V[q[i].v]).Len() : -;
        }
    for (int i=; i<=Q; i++) printf("%d\n",ans[i]);
    return ;
}

POJ1984

HDU5900

区间dp，唯一需要注意的就是转移$[l,r]$整段区间的时候，需要满足$[l+1,r-1]$全部被取到，然后就没有了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 310
int T,N,a[MAXN],b[MAXN];
LL sum[MAXN],dp[MAXN][MAXN];
inline int Gcd(int a,int b) {if (!b) return a; else return Gcd(b,a%b);}
int main()
{
    T=read();
    while (T--)
        {
            N=read();
            for (int i=; i<=N; i++) a[i]=read();
            for (int i=; i<=N; i++) b[i]=read(),sum[i]=sum[i-]+b[i];
            memset(dp,,sizeof(dp));
            for (int i=; i<=N-; i++) dp[i][i+]=Gcd(a[i],a[i+])!=? b[i]+b[i+]:;
            for (int len=; len<=N; len++)
                for (int l=,r=l+len-; l+len-<=N; l++,r++)
                    {
                        if (dp[l+][r-]==sum[r-]-sum[l+-])
                            dp[l][r]=dp[l+][r-]+(Gcd(a[l],a[r])!=? b[l]+b[r]:);
                        for (int k=l; k<=r-; k++)
                                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+][r]);
                    }
            printf("%lld\n",dp[][N]);
        }
    return ;
}

HDU5900

POJ3162

三次dfs求出各点到直径两端的距离，然后答案可以利用两个指针，用单调队列维护一下。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 1000100
int N,M;
struct EdgeNode{int next,to,dis;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v,int w) {cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; edge[cnt].dis=w; head[u]=cnt;}
inline void InsertEdge(int u,int v,int w) {AddEdge(u,v,w); AddEdge(v,u,w);}
int deep[MAXN],L,side,dis[MAXN];
inline void DFS(int now,int last)
{
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            deep[edge[i].to]=deep[now]+edge[i].dis,
            DFS(edge[i].to,now);
    if (deep[now]>L) L=deep[now],side=now;
    dis[now]=max(dis[now],deep[now]);
}
inline void GetL()
{
    L=,deep[side=]=; DFS(side,);
    L=,deep[side]=; DFS(side,);
    L=,deep[side]=; DFS(side,);
}
int q1[MAXN],q2[MAXN],l1=,r1,l2=,r2,ans;
int main()
{
    N=read(),M=read();
    for (int i=,fa,di; i<=N; i++) fa=read(),di=read(),InsertEdge(fa,i,di);
    GetL();
//    for (int i=1; i<=N; i++) printf("%d  ",dis[i]); puts("");
    //q1单调减q2单调增
    int l=,r=;
    for (; l<=N && r<=N; r++)
        {
            while (l1<=r1 && dis[q1[r1]]<=dis[r]) r1--;
            q1[++r1]=r;
            while (l2<=r2 && dis[q2[r2]]>=dis[r]) r2--;
            q2[++r2]=r;
            if (dis[q1[l1]]-dis[q2[l2]]>M)
                {
                    ans=max(ans,r-l);
                    while (dis[q1[l1]]-dis[q2[l2]]>M)
                        {
                            l=min(q1[l1],q2[l2])+;
                            while (l1<=r1 && q1[l1]<l) l1++;
                            while (l2<=r2 && q2[l2]<l) l2++;
                        }
                }
        }
    ans=max(ans,r-l);
    printf("%d\n",ans);
    return ;
}

POJ3162

HDU4003

这道题最初自己没想到，可以转化成分组背包来进行dp

$dp[i][j]$表示第$i$个节点用$j$个机器人去遍历子树的方案数，特殊的，$dp[i][0]$表示从之前节点放一个下来遍历完再返回的答案。

然后就可以用类似分组背包的方式dp，非常巧妙。

对于每个根节点$root$，有个容量为$K$的背包;如果它有$i$个儿子，那么就有$i$组物品，价值分别为$dp[son][0],dp[son][1].....dp[son][k]$ ，这些物品的重量分别为$0,1,.....k$

现在要求从每组里选一个物品（且必须选一个物品）装进$root$的背包，使得容量不超过$k$的情况下价值最大。

那么这就是个分组背包的问题了。

但是这里有一个问题，就是每组必须选一个物品。

对于这个的处理，我们先将$dp[son][0]$放进背包，如果该组里有更好的选择，那么就会换掉这个物品，否则的话这个物品就是最好的选择。这样保证每组必定选了一个。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 10010
int N,S,K;
struct EdgeNode{int next,to,dis;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v,int w) {cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].dis=w;}
inline void InsertEdge(int u,int v,int w) {AddEdge(u,v,w); AddEdge(v,u,w);}
int dp[MAXN][];
inline void DFS(int now,int last)
{
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            {
                DFS(edge[i].to,now);
                for (int k=K; k>=; k--)
                    {
                        dp[now][k]+=dp[edge[i].to][]+*edge[i].dis;
                        for (int j=; j<=k; j++)
                            dp[now][k]=min(dp[now][k],dp[now][k-j]+j*edge[i].dis+dp[edge[i].to][j]);
                    }
            }
}
int main()
{
    while (~scanf("%d%d%d",&N,&S,&K))
        {
            cnt=; memset(head,,sizeof(head));
            for (int i=,x,y,z; i<=N-; i++) x=read(),y=read(),z=read(),InsertEdge(x,y,z);
            memset(dp,,sizeof(dp)); DFS(S,);
            printf("%d\n",dp[S][K]);
        }
    return ;
}

HDU4003

POJ3107

求重心，按编号顺序输出所有可能

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 50010
int N;
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN<<],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int size[MAXN],dp[MAXN],root,Sz;
inline void DFS(int now,int last)
{
    size[now]=;
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            {
                DFS(edge[i].to,now);
                size[now]+=size[edge[i].to];
                dp[now]=max(dp[now],size[edge[i].to]);
            }
    dp[now]=max(dp[now],Sz-size[now]);
    if (dp[now]<dp[root]) root=now;
}
int main()
{
    N=read();
    for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
    dp[root=]=Sz=N; DFS(,);
    for (int i=; i<=N; i++) if (dp[i]==dp[root]) printf("%d ",i);
    return ;
}

POJ3107

POJ3140

傻逼题，直接统计答案然后暴力

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 100010
int N,M,T;
struct edgeNode{int u,v;}e[MAXN];
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
LL sum[MAXN],Sum,ans;
int deep[MAXN],a[MAXN];
inline void DFS(int now,int last)
{
    sum[now]=a[now];
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            {
                deep[edge[i].to]=deep[now]+;
                DFS(edge[i].to,now);
                sum[now]+=sum[edge[i].to];
            }
}
inline LL ABS(LL x) {return x>? x:-x;}
int main()
{
    while (N=read(),M=read())
        {
            if (!N && !M) break;
            cnt=; memset(head,,sizeof(head)); Sum=; memset(sum,,sizeof(sum));
            for (int i=; i<=N; i++) a[i]=read(),Sum+=a[i];
            for (int i=; i<=M; i++) e[i].u=read(),e[i].v=read(),InsertEdge(e[i].u,e[i].v);
            DFS(,);
            ans=(1LL<<);
            for (int i=; i<=M; i++)
                {
                    if (deep[e[i].v]>deep[e[i].u]) swap(e[i].u,e[i].v);
                    ans=min(ans,ABS(sum[e[i].u]-(Sum-sum[e[i].u]) ) );
                }
            printf("Case %d: %I64d\n",++T,ans);
        }
    return ;
}

POJ3140

HDU2476

这题又看了题解，自己想到的dp和标算有些差池，但是个人感觉没问题...

先说一下自己的想法，$dp[l][r]$表示区间$[l,r]$的s1和s2匹配的最小代价，这样可以预处理出$dp[i][i]$，然后dp，转移分两种情况，一种是$s2[l]=s2[r]$这样这一段可以直接先同时覆盖，可以从$dp[l+1][r-1]$转移过来，另一种就是枚举断点常规转移，这样再加一点讨论就可以，小数据对拍是没问题的，但是会wa。

正解和我的想法很类似，不过我是直接从s1->s2，而正解是先计算空串到s2的代价，然后再利用其计算s1->s2的代价。

$dp[l][r]$表示从空串的$[l,r]$区间匹配s2的最小代价，也是需要先预处理$dp[i][i]$，然后转移同理，不过稍有不同，$$dp[l][r]=min(dp[l+1][r]+1,dp[l+1][k]+dp[k+1][r](s2[l]=s2[k]) \quad )$$

然后再利用$ans[i]$表示s1->s2的最小代价，转移类似，然后答案就是$ans[N]$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
char s1[],s2[];
int N,dp[][],ans[];
int main()
{
    while (~scanf("%s%s",s1+,s2+))
        {
            N=strlen(s1+);
            memset(dp,,sizeof(dp));
            for (int i=; i<=N; i++) dp[i][i]=;
            for (int len=; len<=N; len++)
                for (int l=,r=l+len-; l+len-<=N; l++,r++)
                    {
                        dp[l][r]=dp[l+][r]+;
                        for (int k=l+; k<=r; k++)
                            if (s2[l]==s2[k])
                                dp[l][r]=min(dp[l][r],dp[l+][k]+dp[k+][r]);
//                        printf("%d %d %d\n",l,r,dp[l][r]);
                    }
            memset(ans,,sizeof(ans));
            ans[]=s1[]==s2[]? :;
            for (int i=; i<=N; i++)
                {
                    ans[i]=dp[][i];
                    if (s1[i]==s2[i]) ans[i]=min(ans[i],ans[i-]);
                    for (int j=; j<=i-; j++)
                        ans[i]=min(ans[i],ans[j]+dp[j+][i]);
                }
            printf("%d\n",ans[N]);
        }
    return ;
}

HDU2476

HDU5438

先拓扑一下，把叶节点标记，然后再用并查集维护一下每个块即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define LL long long
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 100010
int T,N,M,a[MAXN],d[MAXN];
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
bool visit[MAXN];
inline void toposort()
{
    queue<int>q;
    for (int i=; i<=N; i++) if (d[i]<=) q.push(i),visit[i]=;
    while (!q.empty())
        {
            int now=q.front(); q.pop();
            for (int i=head[now]; i; i=edge[i].next)
                if (--d[edge[i].to]==) visit[edge[i].to]=,q.push(edge[i].to);
        }
}
int f[MAXN],size[MAXN];
LL sum[MAXN];
inline int F(int x) {if (f[x]==x) return x; return f[x]=F(f[x]);}
inline void merge(int x,int y)
{
    int fx=F(x),fy=F(y);
    if (fx==fy) return;
    f[fx]=fy;
    size[fy]+=size[fx];
    sum[fy]+=sum[fx];
}
int main()
{
    T=read();
    while (T--)
        {
            cnt=; memset(head,,sizeof(head));
            N=read(),M=read();
            for (int i=; i<=N; i++) a[i]=read();
            memset(d,,sizeof(d));
            for (int i=,x,y; i<=M; i++) x=read(),y=read(),InsertEdge(x,y),d[x]++,d[y]++;
            memset(visit,,sizeof(visit));
            toposort();
            for (int i=; i<=N; i++) f[i]=i,sum[i]=a[i],size[i]=;
            for (int i=; i<=N; i++)
                if (!visit[i])
                    for (int j=head[i]; j; j=edge[j].next)
                        if (!visit[edge[j].to])
                            merge(i,edge[j].to);
//            for (int i=1; i<=N; i++) printf("%d  %d  %d  %d  %I64d\n",i,visit[i],F(i),size[F(i)],sum[F(i)]);
            LL ans=;
            for (int i=; i<=N; i++)
                if (!visit[i] && F(i)==i && size[i]&)
                    ans+=sum[i];
            printf("%I64d\n",ans);
        }
    return ;
}

HDU5438

HDU5293

树形dp，比较巧妙。

$f[x]$表示以$x$为根的子树符合条件的最大价值和，转移需要枚举所有$LCA(u,v)=x$的树链，方程比较显然。$$f[x]=max(f[x],\sum (sum[son]-f[son])+w_{i})$$

其中$sum[x]$表示以$\sum f[son]$，转移很显然是去除$u-->v$路径上的点后所有$deep$最小的子树的和，引用Claris的图：

所以现在要快速的求出绿色部分的和，这个可以利用线段树/树状数组维护dfs序做到$logN$，然后就可以了。

总的时间复杂度$O((N+M)logN)$

多组数据要注意清空，自己忘记清空father导致多WA了很多次，要注意。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define LL long long
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 100010
int T,N,M;
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
struct LineNode{int u,v,w;}l[MAXN];
vector <int> v[MAXN];
int pl[MAXN],dfn,pr[MAXN],deep[MAXN],father[MAXN][];
inline void DFS(int now,int last)
{
    pl[now]=++dfn;
    for (int i=; i<=; i++)
        if (deep[now]>=(<<i))
            father[now][i]=father[father[now][i-]][i-];
        else break;
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            deep[edge[i].to]=deep[now]+,
            father[edge[i].to][]=now,
            DFS(edge[i].to,now);
    pr[now]=++dfn;
}
inline int LCA(int x,int y)
{
    if (deep[x]<deep[y]) swap(x,y);
    int dd=deep[x]-deep[y];
    for (int i=; i<=; i++)
        if (dd&(<<i)) x=father[x][i];
    for (int i=; i>=; i--)
        if (father[x][i]!=father[y][i])
            x=father[x][i],y=father[y][i];
    return x==y? x:father[x][];
}
LL tree[MAXN<<];
inline int lowbit(int x) {return x&-x;}
inline void Modify(int p,int d) {for (int i=p; i<=dfn; i+=lowbit(i)) tree[i]+=d;}
inline LL Query(int p) {LL re=; for (int i=p; i; i-=lowbit(i)) re+=tree[i]; return re;}
LL f[MAXN],g[MAXN];
inline void DP(int now,int last)
{
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=last)
            DP(edge[i].to,now),
            g[now]+=f[edge[i].to];
    f[now]=g[now];
    for (int i=,x; i<v[now].size(); i++)
        x=v[now][i],
        f[now]=max(f[now],g[now]+Query(pl[l[x].u])+Query(pl[l[x].v])+l[x].w);
    Modify(pl[now],g[now]-f[now]);
    Modify(pr[now],f[now]-g[now]);
}
int main()
{
    T=read();
    while (T--)
        {
            N=read(),M=read();
            cnt=; memset(head,,sizeof(head));
            for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
            dfn=; memset(father,,sizeof(father));
            DFS(,);
            for (int i=; i<=N; i++) v[i].clear();
            for (int i=; i<=M; i++) l[i].u=read(),l[i].v=read(),l[i].w=read(),v[LCA(l[i].u,l[i].v)].push_back(i);
            memset(f,,sizeof(f)); memset(g,,sizeof(g)); memset(tree,,sizeof(tree));
            DP(,);
            printf("%lld\n",f[]);
        }
    return ;
}

HDU5293

HDU5290

这个树形dp有点厉害...自己简单说一下，详细题解

两个状态$f[x][k]$表示以$x$为根的子树全部被摧毁还能从$x$节点向上破坏距离$<=k$的点，$g[x][k]$表示以$x$为根的子树内最深的未被破坏的点距离$x$为$k$;

然后利用这两个状态进行转移；

先考虑$x$节点不被选择的转移：

因为$f[x][k]$可以从$x$再向外扩展$k$的距离，所以$f[x][k]$的值可以从至多$g[x][k]$的值转移得到，并且$f[x][k]$成立的条件一定满足存在$f[son][k+1]$成立，所以转移就是：

$$f[x][k]=min(f[x][k],f[son][k+1]+\sum min(f[son'][0..k+1],g[son'][0..k]))$$

所以这种情况下$g[x][k]$转移同理，必须满足存在$g[son][k-1]$，且其余子节点$f[son][k]$不存在，然后就可以得到转移：

$$g[x][k]=min(g[x][k],g[son][k-1]+\sum min(f[son'][0..k],g[son'][0..k-1]))$$

上述两个转移$son$和$son'$都是$x$的子节点，但$son$指的是哪个必须满足的节点，$son'$是指除此之外的其他节点。

再考虑$x$节点被选择的转移：

比上述显然$$f[x][w[x]]=1+\sum min(f[son][0..w[x]],g[son][0..w[x]-1])$$

这样直接dp的复杂度是$O(NM^{2})$的，可以通过处理前缀最小得到$O(NM)$，优化内存可以通过维护$f,g$的单调性。

No Code

留坑

HDU5760

这个区间dp也是比较厉害啊。

要求最长的长度和方案数，很容易想到$O(N^{3})$的dp，但是并不过，那么需要优化这个dp

预处理出$pre[i][j],suf[i][j]$分别表示从$i$这个位置开始它前面的/后面的第一个为$j$的位置。

然后$dp[l][r]$表示$[l,r]$之间的且$a[l]==a[r]$的最长合法回文，$cnt[l][r]$表示合法回文方案数，这时候考虑，$dp[l][r]<=dp[l,r+1...N]$，当区间左端点被固定时，右端点增大，最长合法回文必定不减。

这样就可以简化$N^{3}$的方法中的一维枚举，复杂度降到$O(N^{2})$

这样做的话，由于答案是通过固定左端点，枚举右端点得到，为了保证得到全部区间，左端点从后往前枚举即可。

具体的就是，先初始化$dp[i][i]=cnt[i][i]=1$，然后倒叙枚举左端点，左端点固定枚举右端点；

先用$len$记录当前的最长合法回文长度，$tot$记录当前的合法回文的方案数，然后转移；

当$a[l]==a[r]$时，显然$dp[l][r]=len+2,cnt[l][r]=tot$

当$a[l]>=a[r]$时，就可能需要更新$len$和$tot$的值，令$x=suf[l][a[r]],y=pre[r][a[r]]$，用区间$[x,r]$的值去和当前$len$比较，更新。但是这里的方案数可能会出现部分重复计算的情况，所以应该特判并减去。

具体来说就是如果$dp[x][y]==dp[x][r]$就表示这两个区间方案是相同的，但是又知道$y<r$ 所以，这样就说明$cnt[x][r]$中已经统计过$cnt[x][y]$了，这样$cnt[x][y]$就是重复的部分，就应该减去。

最后枚举$a_{i}$统计答案即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 5050
#define P 1000000007
int N,dp[MAXN][MAXN],cnt[MAXN][MAXN],a[MAXN],ls[MAXN],tp,top;
int pre[MAXN][MAXN],suf[MAXN][MAXN];
int main()
{
    while (~scanf("%d",&N))
        {
            tp=,top=;
            for (int i=; i<=N; i++) a[i]=read(),ls[++tp]=a[i];
            stable_sort(ls+,ls+tp+);
            for (int i=; i<=tp; i++) if (ls[top]!=ls[i]) ls[++top]=ls[i];
            for (int i=; i<=N; i++) a[i]=lower_bound(ls+,ls+top+,a[i])-ls;

            memset(pre,,sizeof(pre));
            memset(suf,,sizeof(suf));
            for (int i=; i<=N+; i++)
                for (int j=; j<=top; j++)
                    if (a[i-]!=j) pre[i][j]=pre[i-][j]; else pre[i][j]=i-;
            for (int i=N; i>=; i--)
                for (int j=; j<=top; j++)
                    if (a[i+]!=j) suf[i][j]=suf[i+][j]; else suf[i][j]=i+;

            memset(dp,,sizeof(dp)); memset(cnt,,sizeof(cnt));
            for (int i=; i<=N; i++) dp[i][i]=,cnt[i][i]=;
            for (int l=N; l; l--)
                for (int r=l+,len=,tot=; r<=N; r++)
                    {
//                        printf("<%d  %d>\n",l,r);
                        if (a[l]==a[r]) dp[l][r]=len+,cnt[l][r]=tot;
                        if (a[l]>=a[r])
                            {
                                int x=suf[l][a[r]],y=pre[r][a[r]];
                                if (dp[x][r]>len) len=dp[x][r],tot=cnt[x][r];
                                    else if (dp[x][r]==len)
                                        {
                                            if (y>=x && dp[x][y]==dp[x][r]) tot=(tot-cnt[x][y]+P)%P;
                                            tot=(tot+cnt[x][r])%P;
                                        }
                            }
                    }
            int len=,tot=;
            for (int i=; i<=top; i++)
                {
                    int l=suf[][i],r=pre[N+][i];
                    if (!l || !r) continue;
                    if (len<dp[l][r]) len=dp[l][r],tot=cnt[l][r];
                        else if (len==dp[l][r]) tot=(tot+cnt[l][r])%P;
                }
            printf("%d %d\n",len,tot);
        }
    return ;
}

HDU5760

HDU4044

这题的题意有点难懂，实际上就是考虑类似保卫萝卜树上版本，然后就可以想出大概了。

和背包模型非常接近，所以考虑用背包求解，但是又不能直接利用背包。

首先对于一个节点$i$，我们可以算出给他$j$的费用，可以得到的最大的power，但是实际发现，对于一个节点$i$，计算这个的过程是分为两部分的：

1.计算以这个节点为根的子树中的“最大”power  2.计算这个节点单独考虑时的最大power

因为破坏可能会下放到任意叶子节点，所以每个分支的答案需要尽可能大，而又相互独立，所以第一部分的计算实际上是找子树的最小的最大。

而这两个部分都可以利用分组背包求解，然后就可以了。

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 5010
int T,N,M,sz[MAXN],co[MAXN][],po[MAXN][];
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; edge[cnt].to=v; head[u]=cnt;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int dp[MAXN][],g[MAXN];
inline void DFS(int now,int last)
{
    bool leaf=;
    for (int i=head[now]; i && !leaf; i=edge[i].next)
        if (edge[i].to!=last) leaf=;
    if (leaf)
        {
            memset(dp[now],,sizeof(dp[now]));
            for (int i=head[now]; i; i=edge[i].next)
                if (edge[i].to!=last)
                    {
                        DFS(edge[i].to,now);
                        for (int j=M,k,t=; j>=; j--)
                            {
                                for (t=,k=; k<=j; k++)
                                    t=max(t,min(dp[edge[i].to][k],dp[now][j-k]));
                                dp[now][j]=t;
                            }
                        }
        }
    for (int j=M; j>=; j--) g[j]=dp[now][j];
    for (int j=M; j>=; j--)
        {
            for (int i=; i<=sz[now]; i++)
                if (j>=co[now][i])
                    dp[now][j]=max(dp[now][j],g[j-co[now][i]]+po[now][i]);
            g[j]=dp[now][j];
        }
}
int main()
{
    T=read();
    while (T--)
        {
            N=read();
            memset(head,,sizeof(head)); cnt=;
            for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
            M=read();
            for (int i=,j; i<=N; i++)
                for (sz[i]=read(),j=; j<=sz[i]; j++)
                    co[i][j]=read(),po[i][j]=read();
            memset(dp,,sizeof(dp));
            DFS(,);
            printf("%d\n",dp[][M]);
        }
    return ;
}

HDU4044