HDU 2845 Beans

发表于 2011-09-30 | 分类于文章归档 | 阅读次数:

把二维按行列分解然后dp。

dp[i][0]表示不取第i个能到的最大值

所以dp[i][0] = Max(dp[i-1][0],dp[i-1][1]);

dp[i][1]表示取第i个能到的最大值

_所以dp[i][1] = _dp[i-1][0]+value[i];__

row[i]记录下每一行的最优情况,然后再按照上面的方法进行dp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxn 200001
#define Max(a,b) ((a)>(b)?(a):(b))
int dp[Maxn][2];
int value[Maxn];
int row[Maxn];
int M,N;
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int i,j,k;
    while (scanf("%d%d",&M,&N)!=EOF)
    {
        dp[0][0] = 0;dp[0][1] = 0;
        for (i = 1; i <= M; i++)
        {
            for (j = 1; j <= N; j++)
            {
                scanf("%d",&value[j]);
                dp[j][0] = Max(dp[j-1][0],dp[j-1][1]);
                dp[j][1] = dp[j-1][0]+value[j];
            }
            row[i] = Max(dp[N][0],dp[N][1]);
        }
        dp[0][0] = 0;dp[0][1] = 0;
        for (i = 1; i <= M; i++)
        {
            dp[i][0] = Max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0]+row[i];
        }
        printf("%d\n",Max(dp[M][1],dp[M][0]));
    }
    getch();
    return 0;
}

HDU 2844 Coins

发表于 2011-09-24 | 分类于文章归档 | 阅读次数:

多重背包问题，用n个物品，每个物品有价值v[i]，每个物品数量限制为num[i]。

这道题是问，用所有的硬币能够在m的范围内最多可以组合成多少种价值。

对于每个硬币而言:
IF 价值×数量>=m THEN
    取这个硬币的次数相当于无限制，可以考虑成完全背包
ELSE THEN
    考虑成0-1背包（二进制优化），就是把这个硬币的v和num组合出0-1背包可能出现的状态（可以去看背包九讲）

_（对于num，类似于编码。当2^n _<=num/2时：k = 2^n（n=0，1，2，……）表示状态，对应下来就是二进制的某一位数是1，然后还有一个状态就是k>num/2的时候啦，num+1-k，这样下来就可以用k来组合枚举出从1->num的所有可能了。然后对于k，单位价值和大小都乘上k之后就变成了一个0-1背包）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxv 100001
#define Maxn 101
int v[Maxn],num[Maxn];
int knap[Maxv];
int n,m;
void MultipleSack(int v,int num)
{
    int i,j,k;
    int space;
    if (v*num >= m)
    {
        //用完全背包去求
        for (space = v; space <= m; space++)
        {
            knap[space] = knap[space]|knap[space-v];
        }
    }
    //用0-1背包去求，二进制优化
    for (k = 1; k<=num/2; k=(k<<1))
    {
        for (space = m; space >= k*v; space--)
            knap[space] = knap[space]|knap[space-k*v];
    }
    k = num+1-k;
    for (space = m; space >= k*v; space--)
        knap[space] = knap[space]|knap[space-k*v];
    return ;
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int i,j,k,t;
    while (scanf("%d%d",&n,&m),n&&m)
    {
        for (i = 1; i <= n; i++)
            scanf("%d",&v[i]);
        for (i = 1; i <= n; i++)
            scanf("%d",&num[i]);
        memset(knap,0,sizeof(knap));
        knap[0] = 1;
        for (i = 1; i <= n; i++)
            MultipleSack(v[i],num[i]);
        for (i = 1,t = 0; i <= m; i++)
            t += knap[i];
        printf("%d\n",t);
    }
    getch();
    return 0;
}

HDU 2829 Lawrence

发表于 2011-09-21 | 分类于文章归档 | 阅读次数:

题目大意：在一条直线型的铁路上，每个站点有各自的权重num[i]，每一段铁路（边）的权重（题目上说是战略价值什么的好像）是能经过这条边的所有站点的乘积之和.。然后给你m个炮弹，让你选择破坏掉m段铁路，使剩下的整条铁路的战略价值最小。

四边形优化的动态规划，做题时看了别人的解题报告后还不怎么明白四边形优化咋一回事，于是只能贴代码了~

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxn 1010
int dp[Maxn][Maxn];
int value[Maxn][Maxn];
int att[Maxn][Maxn];
int sum[Maxn],num[Maxn];
int n,m;
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int i,j,k;
    int t;
    while (scanf("%d%d",&n,&m),n||m)
    {
        sum[0] = 0;num[0] = 0;
        for ( i = 1; i <= n; i++)
        {
            scanf("%d",&num[i]);
            sum[i] = sum[i-1]+num[i];
        }
        memset(value,0,sizeof(value));
        for ( i = 1; i <= n; i++)
        {
            for(j = i+1; j <= n; j++)
                value[i][j] = value[i][j-1]+(sum[j-1]-sum[i-1])*num[j];
        }
        for (i = 0; i <= n; i++)
        {
            att[i][0] = 0;
            dp[i][0] = value[1][i];
        }
        for (k = 1; k <= m; k++)
        {
            att[n+1][k] = n-1;
            for (i = n; i > k; i--)
            {
                dp[i][k] = dp[k][k-1]+value[k+1][i];
                att[i][k] = k;
                for (j = att[i][k-1]; j <= att[i+1][k]; j++)
                {
                    t = dp[j][k-1] + value[j+1][i];
                    if (t < dp[i][k])
                    {
                        dp[i][k] = t;
                        att[i][k] = j;
                    }
                }
            }
        }
        printf("%d\n",dp[n][m]);
    }
    getch();
    return 0;
}

HDU 2822 Dogs

发表于 2011-09-21 | 分类于文章归档 | 阅读次数:

本题直接用宽搜解决，我是沙茶。如题所述，标记为X的地方可以直接通过（不增加步数），标记为’. ’的地方步数要加1。直接宽搜的话会超时～于是就用两个BFS，两个队列。先调用第一个BFS，如果进入标记是X的地方，则调用第二个BFS2直接先遍历完其他所有相邻的标记为X的区域。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Maxn 1001
#define QSize 1000000
typedef struct
{
    intx;
    inty;
}Node;
typedef struct queue
{
    Node base[QSize];
    inthead;
    inttail;
}queue;
queue Q1,Q2;
voidpush(queue *Q,Node e)
{
    Q->base[Q->tail].x = e.x;
    Q->base[Q->tail].y = e.y;
    Q->tail++;
    if(Q->tail==QSize) Q->tail = 0;
}
Node pop(queue *Q)
{
    Node e;
    e.x = Q->base[Q->head].x;
    e.y = Q->base[Q->head].y;
    Q->head++;
    if(Q->head==QSize)
        Q->head = 0;
    return e;
}
enum boolean{FALSE,TRUE};
const int INF = 0x0fffffff;
char Map[Maxn][Maxn];
int Digs[Maxn][Maxn];
unsigned char Visit[Maxn][Maxn];
int m,n;
int Limit;
int iPlus[4] = {0,-1,1,0};
int jPlus[4] = {-1,0,0,1};
void BFS2(Node s)
{
    int k;
    int go;
    Node pre,next;
    Q2.head = Q2.tail = 0;
    push(&Q2,s);
    while(Q2.head!=Q2.tail)
    {
        pre = pop(&Q2);
        for(k = 0; k < 4; k++)
        {
            next.x = pre.x+iPlus[k];
            next.y = pre.y+jPlus[k];
            if(next.x>=1 && next.x <= m && next.y>=1 && next.y<=n)
            {
                if(Map[next.x][next.y]=='X'&&Digs[next.x][next.y]>Digs[pre.x][pre.y])
                {
                    Digs[next.x][next.y] = Digs[pre.x][pre.y];
                    push(&Q2,next);
                }
                elseif(Digs[next.x][next.y]>Digs[pre.x][pre.y]+1)
                {
                    Digs[next.x][next.y] = Digs[pre.x][pre.y]+1;
                    push(&Q1,next);
                }
            }
        }
    }
}
void BFS(Node s)
{
    int k;
    int go;
    Node pre,next;
    Q1.head = Q1.tail = 0;
    push(&Q1,s);
    Digs[s.x][s.y] = 0;
    while(Q1.head!=Q1.tail)
    {
        pre = pop(&Q1);
        for(k = 0; k < 4; k++)
        {
            next.x = pre.x+iPlus[k];
            next.y = pre.y+jPlus[k];
            if(next.x>=1 && next.x <= m && next.y>=1 && next.y<=n)
            {
                if(Map[next.x][next.y]=='X'&& Digs[next.x][next.y]>Digs[pre.x][pre.y] )
                {
                    Digs[next.x][next.y] = Digs[pre.x][pre.y];
                    BFS2(next);
                }
                elseif(Digs[next.x][next.y]>Digs[pre.x][pre.y]+1)
                {
                    Digs[next.x][next.y] = Digs[pre.x][pre.y]+1;
                    push(&Q1,next);
                }
            }
        }
    }
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    Node Start,End;
    int i,j,k;
    char ch;
    while(scanf("%d%d",&m,&n),m&&n)
    {
        getchar();
        for(i = 1; i <= m; i++)
        {
            for(j = 1; j <= n; j++)
            {
                ch = getchar();
                Map[i][j] = ch;
                Digs[i][j] = INF;
            }
            getchar();
        }
        scanf("%d%d",&Start.x,&Start.y);
        scanf("%d%d",&End.x,&End.y);
            BFS(Start);
        printf("%d\n",Digs[End.x][End.y]);
    }
    getch();
    return 0;
}

HDU 2818 Building Block

发表于 2011-09-20 | 分类于文章归档 | 阅读次数:

挺不错的一道题目,并查集的确是最优美的数据结构之一。

题目大意：有N个piles（按序编号），每次有两种操作：

M x y 表示把x所在的那一堆全部移到y所在的那一堆

C x 询问在x之下有多少个方块

解决方法：使用并查集（路径压缩）实现，然后用count[X]表示X所在的那一堆总共多少个piles，under[x]表示x之下有多少个piles。

首先，每次操作我们合并两个集合（如果原来在同一集合中除外），count[X]是每次操作可以直接实现的,就是把两堆的数目相加，很容易（初始值为1）。那么当某次移动操作发生时，首先确定x所在的那一堆最底部的X以及y所在那一堆最底部的Y，那么under[X]的数目就是另外一堆piles的总数count[Y]，有了这个条件，在接下去的操作中，就可以根据FIND（x）递归去一边寻找根一边更新其他未知的under[x]。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxn 333333
int count[Maxn];   //count[X]：X是集合代表,某个堆(集合)中Piles的总数
int under[Maxn];   //under[i]: 编号为i的Pile下面有多少个Piles (一边进行查找，一边更新)
int parent[Maxn];
int N;
void Init(void)
{
    int i;
    for (i = 0; i <= N; i++)
    {
        parent[i] = i;
        count[i] = 1;
    }
    memset(under,0,sizeof(under));
    return;
}
int FIND(int x)
{
    int tmp;
    if (x!=parent[x])
    {
        tmp = FIND(parent[x]);
        under[x] += under[parent[x]];
//递归过程自底向上自动更新under[],递归基础：下面的under[X] = count[Y]
        parent[x] = tmp;
    }
    return parent[x];
}
void Move(int x,int y)
{
    int X,Y;
    X = FIND(x);
    Y = FIND(y);
    if (X!=Y)
    {
        under[X] = count[Y];             //X是当前堆(集合)中最底部的，直接更新under[]
        count[Y] += count[X];            //直接更新Y这堆(集合)的高度(总共多少个Piles)
        parent[X] = Y;                   //合并
    }
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    char state;
    int i,j;
    int k;
    while (scanf("%d",&N)!=EOF)
    {
        getchar();
        Init();
        while(N--)
        {
            scanf("%c ",&state);
            if (state=='M')
            {
                scanf("%d%d",&i,&j);
                getchar();
                Move(i,j);
            }
            else
            {
                scanf("%d",&i);
                getchar();
                FIND(i);
                printf("%d\n",under[i]);
            }
        }
    }
    getch();
    return 0;
}

HDU 2817 A sequence of numbers

发表于 2011-09-20 | 分类于文章归档 | 阅读次数:

很水的一道题，数论做的很少。这题的输入是一个数列中的前三个数，然后根据输入判断是等差数列还是等比数列，然后求出第n项。囧，高中的公式就不写了～～

需要注意的地方是对结果取摸：A×B%M = ((A%M)*((B%M)%M)

最重要是求等比数列的时候：求幂乘要用二分来乘，否则会TLE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 200907
long long  a1,a2,a3;
long long  d,n,an;
long long cal(long long x,long long a,long long n)
{
    int i;
    for (i = 0; (1LL<<i)<=n;i++)
    {
        if(n&(1LL<<i))
            x = x*a%M;
        a = a*a%M;
    }
    return x;
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    long long T;
    scanf ("%I64d",&T);
    while (T--)
    {
        scanf("%I64d%I64d%I64d%I64d",&a1,&a2,&a3,&n);
        if ( (a2-a1)==(a3-a2) )
        {
            d = a2-a1;
            an = (((a1%M+((n-1)%M)*(d%M)))%M)%M;
        }
        else
        {
            d = a2/a1%M;
            an = cal(a1%M,d,n-1)%M;
        }
        printf("%I64d\n",an);
    }
    getch();
    return 0;
}

HDU 4003 Find Metal Mineral

发表于 2011-09-17 | 分类于文章归档 | 阅读次数:

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4003

大连网络赛的题目（比赛时候几乎就是瞄了一眼而已～囧），然后前两天一直想A掉这题，结果感冒发烧了T_T一直放着，最后也还是看了大牛的题解才写出代码，树形DP还是不行啊～～

这题是树DP，最关键的地方还是对于每个顶点的状态转移，要注意两个地方，一个是DFS控制方向往深处搜索下去（这也是DFS的奥妙），第二点就是类似背包的顶点转移方程。

1
2
3

首先考虑平凡的:
for j<-K to 0: 
    dp[u][j]+={dp[Child][0]+2*边上的代价}

然后对每条边进行转移dp[u][j] = MIN(dp[u][j],dp[u][j-k]+dp[Child][k]+ k个机器人路过这条边的总代价)

晒一下我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxn 10001
typedef struct Node
{
    int NO_;
    int Cost;
    struct Node* NextChild;
}Node;
Node* FirstChild[Maxn];
enum boolean{FALSE,TRUE};
int dp[Maxn][12];
int N,S,K;
void DFS(int u,int From)
{
    int i,j,k;
    int Child;
    Node *p;
    for (p = FirstChild[u]; p!=NULL; p=p->NextChild)
    {
        Child = p->NO_;
        if (Child!=From)
            DFS(Child,u);
    }
    for (p = FirstChild[u];p!=NULL;p=p->NextChild)
    {
        Child = p->NO_;
        if (Child!=From)
        {
            for (j = K; j>= 0; j--)
            {
                dp[u][j] += dp[Child][0]+2*(p->Cost);
                for (k = 0; k <= j; k++)
                    if (dp[u][j-k]+dp[Child][k]+k*(p->Cost)<dp[u][j])
                        dp[u][j] = dp[u][j-k]+dp[Child][k]+k*(p->Cost);
            }
        }
    }
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int i,j,k;
    int u,v,w;
    Node *p;
    while(scanf("%d%d%d",&N,&S,&K)!=EOF)
    {
        memset(FirstChild,0,sizeof(FirstChild));
        for (i = 1; i <= N-1; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            p = (Node*)malloc(sizeof(Node));
            p->Cost = w;
            p->NO_ = v;
            p->NextChild = FirstChild[u];
            FirstChild[u] = p;
            p = (Node*)malloc(sizeof(Node));
            p->Cost = w;
            p->NO_ = u;
            p->NextChild = FirstChild[v];
            FirstChild[v] = p;
        }
        memset(dp,0,sizeof(dp));
        DFS(S,-1);
        printf("%d\n",dp[S][K]);
    }
    getch();
    return 0;
}

HDU 2586 How far away ？

发表于 2011-09-17 | 分类于文章归档 | 阅读次数:

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586

题目是说：N个顶点形成树，接下来有M次询问两个顶点间的距离～

解题思路：用Tarjan脱机最小公共祖先算法（
P319）

然后计算两个顶点到根部的距离加起来与他们公共祖先到根部的距离乘以2的绝对值

Dist(u,v) = abs(dist[u]+dist[v]-2*dist[ancestor[v]]);

Tarjan算法我是看着敲出来了，书上习题有几个证明自己还没去做，这两天感冒发烧，解释什么的先不写了，也写不来
（我觉得里面好像还很多问题）

晒一下我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define Maxn 40001
typedef struct Node
{
    int NO_;
    int D;
    struct Node *NextChild;
}Node;
Node* FirstChild[Maxn];
int ancestor[Maxn];
int p[Maxn];
int rank[Maxn];
int dist[Maxn];
enum boolean{FALSE,TRUE};
enum COLOR{WHITE,BLACK};
unsigned char color[Maxn];
unsigned char Visit[Maxn];
void MAKE_SET(int x)
{
    p[x] = x;
    rank[x] = 0;
}
void LINK(int x,int y)
{
    if (rank[x]>rank[y])
        p[y] = x;
    else
    {
        p[x] = y;
        if (rank[x]==rank[y])
            rank[y]++;
    }
}
void UNION(int x,int y)
{
    LINK(FIND_SET(x),FIND_SET(y));
}
int FIND_SET(x)
{
    if ( x!=p[x] )
        p[x] = FIND_SET(p[x]);
    return p[x];
}
void LCA(int u)
{
    if (Visit[u])
        return;
    Visit[u] = TRUE;
    int v;
    MAKE_SET(u);
    ancestor[FIND_SET(u)] = u;
    Node *p;
    for (p = FirstChild[u]; p; p=p->NextChild)
    {
        v = p->NO_;
        dist[v] = dist[u] + p->D;
        LCA(v);
        UNION(u,v);
        ancestor[FIND_SET(u)] = u;
    }
    color[u] = BLACK;
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int T;
    int n,m;
    int i,j,k;
    int u,v,w;
    Node *p;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        memset(FirstChild,NULL,sizeof(FirstChild));
        memset(Visit,FALSE,sizeof(Visit));
        memset(dist,0,sizeof(dist));
        for (i = 1; i <= n-1; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            p = (Node*)malloc(sizeof(Node));
            p->NO_ = v;
            p->D = w;
            p->NextChild = FirstChild[u];
            FirstChild[u] = p;
            p = (Node*)malloc(sizeof(Node));
            p->NO_ = u;
            p->D = w;
            p->NextChild = FirstChild[v];
            FirstChild[v] = p;
        }
        LCA(1);
        for (i = 1; i <= m; i++)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",abs(dist[u]+dist[v]-2*dist[ancestor[v]]));
        }
    }
    getch();
    return 0;
}

HDU 1520 Anniversary party

发表于 2011-09-15 | 分类于文章归档 | 阅读次数:

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1520

最基本的树形DP，题目描述了一个学校的员工的分布按树的结构。每个员工对应一个快乐指数，在树中选取员工（约束条件：每个员工和他的直属上司不能同时选取，就是孩子结点和父亲结点不能够共存），然后使选取的员工的快乐指数之和达到最大值。

用dp[i][0]表示选取第i个员工，不包括员工自己时的最大快乐指数和。
dp[i][1]表示选取第i个员工，包括员工自己时的最大快乐指数和。

对于每个结点：
dp[i][0] = 所有孩子结点的最大快乐指数和
dp[i][1] = 自己的快乐指数+所有孩子不包括孩子自身时的最大快乐指数之和

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxn 6001
enum boolean {FALSE,TRUE};
int Happy[maxn];
int N;
int Tree[maxn][maxn];
int Pre[maxn];
int NodeCount[maxn];
int Visit[maxn];
int dp[maxn][2];
int MAX(int x,int y) { return x>y?x:y;}
void DFS(int p)
{
    int Child,i,j,k;
    Visit[p] = TRUE;
    if (NodeCount[p]==-1)
    {
        dp[p][0] = 0;
        dp[p][1] = Happy[p];
        return;
    }
    dp[p][1]+=Happy[p];
    for (i = 0; i <= NodeCount[p]; i++)
    {
        Child = Tree[p][i];
        if (!Visit[Child])
        {
            DFS(Child);
            dp[p][0]+=MAX(dp[Child][1],dp[Child][0]);
            dp[p][1]+=dp[Child][0];
        }
    }
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int L,K,i,j;
    int m;
    while (scanf("%d",&N)!=EOF)
    {
        for (i = 1; i <= N; i++)
            scanf("%d",&Happy[i]);
        memset(NodeCount,-1,sizeof(NodeCount));
        memset(Pre,-1,sizeof(Pre));
        while(scanf("%d%d",&L,&K),L||K)
        {
            Tree[K][++NodeCount[K]] = L;
            Pre[L] = K;
        }
        memset(Visit,FALSE,sizeof(Visit));
        memset(dp,0,sizeof(dp));
        m = 0;
        for (j = 1; j <= N; j++)
        {
            if (Pre[j]==-1)
            {
                DFS(j);
                m+=MAX(dp[j][0],dp[j][1]);
            }
        }
        printf("%d\n",m);
    }
    getch();
    return 0;
}

HDU 1011 Starship Troopers

发表于 2011-09-15 | 分类于文章归档 | 阅读次数:

题目链接：http://acm.hdu.edu.cn/status.php?user=XHC91&pid=1011&status=5

这题是一道树形DP，从1号顶点进入树中，每次可以分配小兵到其他可达的顶点去，杀死所有的bugs可以获取brain值，求出m个小兵最多能获取多少brain值。这题要对顶点进行DFS一搜到底，然后用背包的方法选取孩子节点中最多的brain。

对于一个父母顶点，除去它的brain和cost之后，剩下的问题就是一个大小为m-cost的背包了，再由它的孩子节点中任意选取顶点顶点，最终必获得父母顶点的最大值。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxn 222
enum boolean {FALSE,TRUE};
int dp[maxn][maxn];
struct room
{
    int bugs;
    int p;
}room[maxn];
int Tree[maxn][maxn];
int NodeCount[maxn];
int Visit[maxn];
int N,M;
int MAX(int x,int y)
{
    return x>y?x:y;
}
int DFS(int p)
{
    int i,j,k;
    int child;
    int mcost;
    Visit[p] = TRUE;
    mcost = (room[p].bugs+19)/20;
    for (i = mcost; i <= M; i++)
        dp[p][i] = room[p].p;
    for (i = 0; i <= NodeCount[p]; i++)
    {
        child = Tree[p][i];
        if (!Visit[child])
        {
            DFS(child);
            for ( j = M; j>=mcost;j--)
                for (k = 1; j+k<= M; k++)  
                    if (dp[child][k])
                        dp[p][j+k] = MAX(dp[p][j+k],dp[p][j]+dp[child][k]);
            }
        }
    }
    return TRUE;
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int i,j,k;
    int u,v;
    while (scanf("%d%d",&N,&M),N>=0||M>=0)
    {
        for (i = 1; i <= N; i++)
            scanf("%d%d",&room[i].bugs,&room[i].p);
        memset(NodeCount,-1,sizeof(NodeCount));
        memset(dp,0,sizeof(dp));
        memset(Visit,FALSE,sizeof(Visit));
        for (i = 1; i <= N-1; i++)
        {
            scanf("%d%d",&u,&v);
            Tree[u][++NodeCount[u]] = v;
            Tree[v][++NodeCount[v]] = u;  
        }
        if (!M)
            printf("0\n");
        else
        {
            DFS(1);
            printf("%d\n",dp[1][M]);
        }
    }
    getch();
    return 0;
}