Description: 

树上每个点有容量,花费,价值。你有mm元钱,问选出一个连通块的最大价值。

Solution: 

问题在于必须选出一个连通快。每次树形dp时改动一下，递归子树时去掉一份下一个节点的花费，强制选择下一个节点一次，这样就是选择一个联通块了，每次背包二进制分解一下，再用点分治优化即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 505;
int n, m, root, ans;
vector<int> G[N];
int vis[N], mx[N], sz[N], w[N], c[N], d[N], dp[N][4005];
int getsize(int u, int last) {
    int ret = 1;
    for(int i = 0; i < G[u].size(); ++i) {
        if(G[u][i] != last && !vis[G[u][i]]) {
            ret += getsize(G[u][i], u);
        }
    }
    return ret;
}
void findroot(int u, int last, int S) {
    mx[u] = 0;
    sz[u] = 1;
    for(int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if(v != last && !vis[v]) {
            findroot(v, u, S);
            sz[u] += sz[v];
            mx[u] = max(mx[u], mx[v]);
        }
    }
    mx[u] = max(mx[u], S - sz[u]);
    if(mx[u] < mx[root]) {
        root = u;
    }
}
void dfs(int u, int last, int m) {
    if(m <= 0) {
        return;
    }
    for(int i = 0, j = d[u]; j; ++i) {
        if(j >= (1 << i)) {
            for(int W = c[u] << i, V = w[u] << i, k = m; k >= W; --k) {
                dp[u][k] = max(dp[u][k], dp[u][k - W] + V);
            }
            j -= 1 << i;
        } else {
            for(int W = c[u] * j, V = w[u] * j, k = m; k >= W; --k) {
                dp[u][k] = max(dp[u][k], dp[u][k - W] + V);
            }
            j = 0;
        }
    }
    for(int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if(v != last && !vis[v]) {
            for(int j = 0; j <= m - c[v]; ++j) {
                dp[v][j] = dp[u][j];
            }
            dfs(v, u, m - c[v]);
            for(int j = c[v]; j <= m; ++j) {
                dp[u][j] = max(dp[u][j], dp[v][j - c[v]] + w[v]);
            }
        }
    }
}
void solve(int u) {
    root = 0;
    findroot(u, 0, getsize(u, 0));
    vis[root] = 1;
    memset(dp[root], 0, sizeof(dp[root]));
    dfs(root, 0, m - c[root]);
    for(int i = 0; i <= m - c[root]; ++i) {
        ans = max(ans, dp[root][i] + w[root]);
    }
    for(int i = 0; i < G[root].size(); ++i) {
        if(!vis[G[root][i]]) {
            solve(G[root][i]);
        }
    }
}
int main() {
    int T;
    scanf("%d", &T);
    mx[0] = 0x3f3f3f3f;
    while(T--) {
        ans = 0;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
            vis[i] = 0;
            scanf("%d", &w[i]);
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &c[i]);
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &d[i]);
            --d[i];
        }
        for(int i = 1; i < n; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        solve(1);
        printf("%d\n", ans);
    }
    return 0;
}

/*
树的分治
因为树的点权值可达到10^15，注意手动扩栈，还有int64
题意:给你一棵树，给你一些素数，给你每个点一个权值且每个权值均可由这些素数组成。现在定义任意任意两点的价值为他们路径上的权值相乘。求这样的点对的权值为立方数的个数
解：
如果直接求得话会超int64，不可行
由立方数的性质可得，一个数可有素数组成，对于这些素数可以分解为这些素数相乘的形式如，24=(2^3)*(3^1)；如果是立方数的话那么他的各进制对3取余都为0.股24可写成01这种三进制形式
对于这些权值的乘法可有三进制想加可得。
接下来就是树的分治了
当然这里可以先求出一条子树上的各个点的权值乘积，然后和根节点和其他字树比较看是否可以互补那么就找到一对
可用map容器实现。因为他重点是比较到根节点和其他子树是否可以互补，进而递归下去，求出每个子树的这样的点对。
*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<map>
#define ll  __int64
#define N 51000
#define inf 0x3fffffff
using namespace std;
struct node {
 ll u,v,next;
}bian[N*4];
ll yong,head[N];
ll num[N],nn,all[N][51],ff[N][51],minn,m,vis[N],fp[N],ma;
ll prime[51],len;
map<ll,ll>q;
void init() {
 yong=0;
 memset(head,-1,sizeof(head));
}
void addedge(ll u,ll v) {
bian[yong].u=u;
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
void dfs1(ll u,ll fa) {//找到每次根子树的的节点数目
    ll i;
    nn++;
    for(i=head[u];i!=-1;i=bian[i].next) {
        ll v=bian[i].v;
        if(v!=fa&&!vis[v])
            dfs1(v,u);
    }
    return ;
}
ll Max(ll v,ll vv) {
return v>vv?v:vv;
}
void dfs2(ll u,ll fa) {//找重心
 num[u]=1;
 ll i,tit=0;
 for(i=head[u];i!=-1;i=bian[i].next) {
    ll v=bian[i].v;
    if(v!=fa&&!vis[v]) {
        dfs2(v,u);
        num[u]+=num[v];
        tit=Max(tit,num[v]);
    }
 }
 tit=Max(tit,nn-num[u]);
 if(tit<minn) {
    minn=tit;
    ma=u;
 }
 return ;
}
void dfs4(ll u,ll fa) {
 ll i;
 //prllf("dfs4=%d",u);
 if(fa!=-1) {
        ll  e=fp[fa];
    for(i=1;i<=m;i++)
        all[len][i]=(all[e][i]+ff[u][i])%3;
 }
 else {
    for(i=1;i<=m;i++)
        all[len][i]=ff[u][i];
 }
 fp[u]=len++;
 for(i=head[u];i!=-1;i=bian[i].next) {
    ll v=bian[i].v;
    if(v!=fa&&!vis[v])
        dfs4(v,u);
 }
 return ;
 }
ll dfs3(ll u) {//求以当前子树为根的符合条件的对数
   ll i,ans=0,j,k;
   ll s1,s2;
   s1=0;
   q.clear();
   for(i=1;i<=m;i++)
    s1=s1*3+ff[u][i];
  if(s1==0)ans++;
   //prllf("ma=%d,s1=%d\n",ma,s1);
    q[s1]=1;
    for(i=head[u];i!=-1;i=bian[i].next) {
        ll v=bian[i].v;
        if(vis[v])continue;
        len=0;
        dfs4(v,-1);
     //  prllf("len=%d\n",len);
        for(j=0;j<len;j++) {//进行互补
            s1=0;
            for(k=1;k<=m;k++)
                s1=s1*3+(3-all[j][k])%3;
        //  prllf("zzs1=%d\n",s1);
                ans+=q[s1];
        }
        for(j=0;j<len;j++) {
            s2=0;
            for(k=1;k<=m;k++)
                s2=s2*3+(all[j][k]+ff[u][k])%3;//到根结点的权值，为下次互补做准备，同时避免重复
            q[s2]++;
        }
      //  prllf("aad%d\n",ans);
    }
    return ans;
}
ll dfs(ll u) {
  minn=inf;
  nn=0;
  dfs1(u,-1);
  dfs2(u,-1);//求重心
  vis[ma]=1;
  ll ans=dfs3(ma);
 // prllf("ma=%d\n",ma);
  //prllf("ans=%d\n",ans);
  ll i;
  for(i=head[ma];i!=-1;i=bian[i].next) {
    ll v=bian[i].v;
    if(!vis[v])
        ans+=dfs(v);
  }
  return ans;
}
int main() {
      ll n,i,j,k,kk;
      while(scanf("%I64d",&n)!=EOF) {
       init();
       scanf("%I64d",&m);
       for(i=1;i<=m;i++)
        scanf("%I64d",&prime[i]);
       for(i=1;i<=n;i++) {
        scanf("%I64d",&k);
          for(j=1;j<=m;j++) {
            kk=0;
            while(k%prime[j]==0) {
                k/=prime[j];
                kk++;
                kk%=3;
            }
            ff[i][j]=kk;
          }
       }
       for(i=1;i<n;i++) {
        scanf("%I64d%I64d",&j,&k);
        addedge(j,k);
        addedge(k,j);
       }
       memset(vis,0,sizeof(vis));
       printf("%I64d\n",dfs(1));
      }
return 0;}


转载于:https://www.cnblogs.com/thefirstfeeling/p/4410595.html

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5091
思路：扫描线的陈题，先线段树的功能，区间价值，维护的是区间上的最大值，然后将每个敌方单位分解成两个事件，不断更新就行。


code：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=70050;
const int maxt=30500;
const int mo=20005;

struct sg_tree
{
    int l,r;
    int col,rmax;
} ss[maxn<<2];

struct Thing
{
    int l,r,y,kind;
} P[maxt];

int n;
int nn,w,h,ta;

void Push_up(int k)
{
    ss[k].rmax=max(ss[(k<<1)+1].rmax,ss[(k<<1)+2].rmax);
}
void Push_down(int k)
{
    ss[(k<<1)+1].col+=ss[k].col;
    ss[(k<<1)+2].col+=ss[k].col;
    ss[(k<<1)+1].rmax+=ss[k].col;
    ss[(k<<1)+2].rmax+=ss[k].col;
    ss[k].col=0;
}
void Build(int k,int l,int r)
{
    ss[k].col=0;
    ss[k].rmax=0;
    ss[k].l=l;
    ss[k].r=r;
    if(r==l) return ;
    Build((k<<1)+1,l,(l+r)/2);
    Build((k<<1)+2,(l+r)/2+1,r);
}
void init(int nn)
{
    n=1;
    while(n<nn) n*=2;
    Build(0,0,n-1);
}
void update(int a,int b,int k,int cc)
{
    if(b<ss[k].l||a>ss[k].r) return ;
    if(a<=ss[k].l&&ss[k].r<=b){
        ss[k].col+=cc;
        ss[k].rmax+=cc;
    }
    else{
        int mid=(ss[k].l+ss[k].r)/2;
        Push_down(k);
        update(a,b,(k<<1)+1,cc);
        update(a,b,(k<<1)+2,cc);
        Push_up(k);
    }
}
int query(int a,int b,int k)
{
    if(a<=ss[k].l&&ss[k].r<=b) return ss[k].rmax;
    else{
        int v1,v2;
        v1=v2=0;
        int mid=(ss[k].l+ss[k].r)/2;
        if(a<mid) v1=query(a,b,(k<<1)+1);
        if(b>mid) v2=query(a,b,(k<<1)+2);
        return max(v1,v2);
    }
}

bool cmp(Thing A,Thing B)
{
    if(A.y==B.y) return A.kind<B.kind;
    return A.y<B.y;
}

//最佳的放置状态下 矩阵的一边肯定是和每个节点重合
//我们假设左边是和敌人节点重叠的
//那么对每个敌方单位他能被包含的区域就是x+w
//对于每个敌方单位我们构造两种事件 l,r都为x和x+w y为y和y+h+1 kind分别为1和-1
//然后把所有事件按y的坐标排序 一次进行执行即可
//每次执行后都用根节点的值来更新res
void creat(int x,int y)
{
    x+=mo; y+=mo;
    P[ta].l=x; P[ta].y=y;
    if(x+w<=50000) P[ta].r=x+w;
    else P[ta].r=50000;
    P[ta++].kind=1;

    P[ta].l=P[ta-1].l;
    P[ta].r=P[ta-1].r;
    if(y+h+1<=50000) P[ta].y=y+h+1;
    else P[ta].y=50000;
    P[ta++].kind=-1;
}

int main()
{
    int x,y,res;
    while(scanf("%d",&nn),nn>=0){
        scanf("%d%d",&w,&h);
        res=ta=0;
        for(int i=0;i<nn;i++){
            scanf("%d%d",&x,&y);
            creat(x,y);
        }
        init(50005);
        sort(P,P+ta,cmp);
        //for(int i=0;i<ta;i++){
           // printf("l=%d r=%d y=%d kind=%d\n",P[i].l,P[i].r,P[i].y,P[i].kind);
       // }
        for(int i=0;i<ta;i++){
            update(P[i].l,P[i].r,0,P[i].kind);
            res=max(res,ss[0].rmax);
        }
        printf("%d\n",res);
    }
    return 0;
}

摘要：

虽然协同过滤是个性化推荐的主流技术，但它只对用户-项目交互进行建模，不能为推荐提供具体的理由。与此同时，与用户-项目交互相关的丰富的侧信息(例如，用户统计数据和项目属性)提供了有价值的证据，说明为什么推荐适合于用户，但在提供解释方面还没有得到充分的探索。

在技术方面，基于嵌入的方法，例如广泛和深入的神经因子分解机，提供最先进的推荐性能。然而，它们的工作原理就像一个黑匣子，预测背后的原因无法明确地呈现出来。另一方面，决策树等基于树的方法通过从数据中推断决策规则来进行预测。虽然可以解释，但它们不能推广到不可见的特性交互，因此在协作过滤应用程序中会失败。在这项工作中，我们提出了一个新的解决方案，称为树增强嵌入方法结合了基于嵌入和基于树的模型的优点。我们首先使用一个基于树的模型来学习明确的决策规则（交叉特征)来自丰富的侧面信息。接下来，我们设计了一个嵌入模型，该模型可以包含显式交叉特征，并推广到用户ID和项目ID上不可见的交叉特征。嵌入方法的核心是一个易于解释的注意力网络，使得推荐过程完全透明和可解释。我们对旅游景点和餐厅推荐两个数据集进行了实验，证明了我们的解决方案的优越性能和可解释性。

相关工作：

我们大致可以将解释风格分为基于相似性和基于内容的类别。基于相似性的方法以最相似的用户或项目列表的形式给出解释。例如，Behnoush等人的使用限制玻尔兹曼机来计算top-K推荐列表中项目的可解释性得分。虽然基于相似性的解释可以作为解释CF推荐的通用解决方案，但缺点是它缺乏具体的推理。基于内容的作品考虑了各种侧面信息，从项目标签[38,40]、社会关系[31,37]、用户的上下文评论[13,15,28,31,48]到知识图谱，

结论：

本文提出了一种树增强嵌入方法(TEM)，它无缝地结合了基于嵌入模型的泛化能力和基于树的模型的可解释性。由于基于树的部分具有明显的交叉特征和易于解释的注意网络，我们的解决方案的整个预测过程是完全透明和自解释的。同时，TEM

可以达到与目前最先进的推荐方法相媲美的性能。在未来，我们将把TEM扩展到三个方向。首先，我们尝试联合学习基于树和基于嵌入的模型，而不是分别对两个组件建模。这可以促进两个组件之间的信息传播。其次，我们考虑其他上下文信息，如时间、位置和用户情绪，以进一步丰富我们的解释能力。第三，我们将探讨将知识图和逻辑规则引入TEM的有效性

以下是自己的理解，欢迎指错。

1.CF利用user-item的历史交互记录，来计算用户或用户的相似性，从而进行top-k推荐，但放弃了其他额外的信息。在解释性方面，推荐的原因仅仅是你的朋友也喜欢，或者是和你购买的东西很相似，这是不足以让人信服的。

解决的问题：增强推荐可解释性的同时，增强推荐的准确度。
	
提出的模型：TEM = tree + embedding ， 基于embedding的方法具有较强的泛化能力，但一旦额外信息丰富就会失去可解释性。基于tree的方法，既可以做到显性预测，生成的交叉特征可直接解释，但对于未观察到的数据是不能预测。                 在TEM中，有两大重要部分，embedding和attention，embedding向量用于捕获交叉特征之间的相关性，使用GDBT和基于嵌入的协同过滤，把交叉特征投影到嵌入向量中；attetion具体模拟交叉特征的个性化权重，使用的是多层感知器MLPs。
	
具体方案：TEM 由两个模型组成，首先（explicity），利用GBDT在额外信息上有效地区分交叉特征，然后（explainable），将最有预测能力的交叉特征输入到一个基于嵌入的模型，该模型是neural attention network，根据预测对交叉特征重新加权。在tree中，每条path可看做一个交叉特征，叶子结点可看做这条path的预测值。GBDT梯度增强决策树，通过增加树 的数量来增强预测。后期，根据用户反馈，可以局部修改交叉特征，并修改相应的注意力权重，从而不用重新训练模型，就可以更新预测，并重排推荐列表。