飞机票： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5040

从这一题我对2-sat有更深的了解了。。。起先以为2-sat要添加一定可行的边。。。其实不然。。。要求添加可能可以的边。。。意思就是说两个组每个组2个人A1 A2,B1,B2 如果A1选了不能选B1，那么不管A2选了能不能选B1。。。都添加A2 B1这条边搞了一天2-sat 什么鬼~~~反正现在深入了解了。。。好了。。直接正题~~~

分析。。这题就是说给你n个组。每个组有两个球。。每个球有坐标。。从每个组里选择一个球。。且所有球不重叠。。。球最大球径是多少。。。其实就是2-sat问题。。。怎么搞呢？？先求出每队之间的距离。。。即一共有四个距离。。。即(A1,B1),(A1,B2),(A2,B1),(A2,B2) 三维距离很简单。。。((x1-x2）^2+(y1-y2)^2+(z1-z2)^2)^0.5即可。。搜噶然后二分球径。。。这里可以剪下枝。。。怎么搞呢。。。先从上面的距离选出最大的距离作为r,l为0。。。然后在循环里面可以判断下那四个距离是否都小于R，如果小于R。。则不符合条件。。直接继续二分。。。如果有一个可以则。。。根据2-sat建边。。。这里得知道要添加可能的边（起先不知道。。Wa到死）一共有四种可能。。所以有4种添边方案。。。然后每次二分跑一下tarjan。。。如果符合条件。。则l变为mid+e...这里e是定义的精度。。。如果不可以。。那r就要变为mid-e...当可行的时候。。。可以定义一个double记录最大符合条件的球径。。。其实起先我还卡了一下为什么距离要跟球径的两倍比较。。。后来想了一下球可以转的啊。。。太菜了。。。最后精度又是个问题。。。但是只要保留4位小数就可以了。。。因为是spj。。。然后啪啪啪！！！AC！！！

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=456;
const double e=0.0001;
struct he
{
    int a,b,c;
} JLJ[maxn];
vector<int> V[maxn];
double dist[maxn][maxn];
int n;
void init()
{
    for(int i=0; i<n; i++)
    {
        scanf("%d%d%d",&JLJ[i*2].a,&JLJ[i*2].b,&JLJ[i*2].c);
        scanf("%d%d%d",&JLJ[i*2+1].a,&JLJ[i*2+1].b,&JLJ[i*2+1].c);
    }

}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
double cal(double a,double b,double c,double d,double e,double f)
{
    return sqrt((a-d)*(a-d)+(b-e)*(b-e)+(c-f)*(c-f));
}
void play()
{
    double MAX=0;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            dist[i*2][j*2]=cal(JLJ[i*2].a,JLJ[i*2].b,JLJ[i*2].c,JLJ[j*2].a,JLJ[j*2].b,JLJ[j*2].c);
            dist[i*2][j*2+1]=cal(JLJ[i*2].a,JLJ[i*2].b,JLJ[i*2].c,JLJ[j*2+1].a,JLJ[j*2+1].b,JLJ[j*2+1].c);
            dist[i*2+1][j*2]=cal(JLJ[i*2+1].a,JLJ[i*2+1].b,JLJ[i*2+1].c,JLJ[j*2].a,JLJ[j*2].b,JLJ[j*2].c);
            dist[i*2+1][j*2+1]=cal(JLJ[i*2+1].a,JLJ[i*2+1].b,JLJ[i*2+1].c,JLJ[j*2+1].a,JLJ[j*2+1].b,JLJ[j*2+1].c);
            MAX=max(MAX,dist[i*2][j*2]);
            MAX=max(MAX,dist[i*2][j*2+1]);
            MAX=max(MAX,dist[i*2+1][j*2]);
            MAX=max(MAX,dist[i*2+1][j*2+1]);
        }
    }
    double l=0;
    double r=MAX;
    double over=0;
    while(l<=r)
    {
        double mid=(l+r)/2;
        double d=mid*2;
        bool flag=1;
        for(int i=0; i<=2*n; i++)V[i].clear();
        for(int i=0; i<n; i++)
        {  if(!flag)break;
            for(int j=i+1; j<n; j++)
            {
                if(dist[i*2][j*2]<d&&dist[i*2+1][j*2]<d&&dist[i*2][j*2+1]<d&&dist[i*2+1][j*2+1]<d)
                {
                    flag=0;
                    break;
                }
                if(dist[i*2][j*2+1]<d)
                {
                    V[i*2].push_back(j*2);
                    V[j*2+1].push_back(i*2+1);
                }
                if(dist[i*2][j*2]<d)
                {
                        V[i*2].push_back(j*2+1);
                        V[j*2].push_back(i*2+1);
                }
                if(dist[i*2+1][j*2+1]<d)
                {
                    V[i*2+1].push_back(j*2);
                    V[j*2+1].push_back(i*2);
                }
                if(dist[i*2+1][j*2]<d)
                {
                    V[i*2+1].push_back(j*2+1);
                    V[j*2].push_back(i*2);
                }

            }
        }
        if(!flag){
            r=mid-e;
            continue;
        }
        indexx=cntnum=0;
        scnt=-1;
        memset(dfn,-1,sizeof(dfn));
        memset(instack,0,sizeof(instack));
        for(int i=0; i<2*n; i++)
        {
            if(dfn[i]==-1)tarjan(i);
        }
        for(int i=0; i<n; i++)
        {
            if(belong[i*2]==belong[i*2+1])
            {
                flag=0;
                break;
            }
        }
        if(!flag)
        {
            r=mid-e;
            continue;
        }
        over=max(over,l);
        l=mid+e;

    }
    printf("%.4lf\n",over);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4879

分析：搞了一天的2-sat了。。。感觉还是迷迷糊糊真是菜比~~~好了。。。不扯了。。。直接正题：

题意：题意就是给你个矩阵。。。然后求是否有数组满足那段程序的。。。程序自己看啊。。。请点击飞机票。。。这种题怎么变成2-sat。。。烧脑烧力啊。。。，先预处理对角线是否为0和对称点是否一样。。然后只要把每个位单独处理即可~~~。。。坦白地说：对于矩阵的一个元素b[i][j]。。。如果i%2==0&&j%2==0则a[i]&a[j]=b[i][j]。。。这里就可以用到前面文章的内容了。。。就是说a[i]的第k为&a[j]的第k位=b[i][j]的第k位（注：2进制下）然后运用前面文章的信息。不妨设当前点i为1则是i*2,为0则是i*2+1那么就可以建图了

AND 结果为1：建边 x*2+1->x*2,y*2+1->y*2 （两个数必须全为1）

AND 结果为0：建边 y*2->x*2+1,x*2->y*2+1 （两个数至少有一个为0）

OR 结果为1：建边 x*2+1->y*2,2*y+1->x*2 （两个数至少有一个为1）

OR 结果为0：建边 x*2->x*2+1,y*2->y*2+1 （两个数必须全为0）

XOR 结果为1：建边 x*2->y*2+1,y*2->x*2+1,y*2+1->x*2,x*2+1->y*2 （两个数必须不同）

XOR 结果为0：建边 x*2->y*2,y*2->x*2,x*2+1->y*2+1,y*2+1->x*2+1 （两个数必须相同）

这样要处理最多30次。。。因为b[i][j]有范围限制，然后每一次都跑一遍。。。只要有不符合就直接啪啦：NO，如果都想。。YES！啪啪啪~但是速度不快啊。。。不过AC还是轻轻松松的~~~

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
vector<int> V[maxn];
int ai[567][567];
int n;
void init()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            scanf("%d",&ai[i][j]);
        }
    }

}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    for(int i=0; i<n; i++)
    {
        if(ai[i][i]!=0)
        {
            printf("NO\n");
            return;
        }
    }
    int MAX=0;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {   MAX=max(MAX,ai[i][j]);
            if(ai[i][j]!=ai[j][i])
            {
                printf("NO\n");
                return;
            }
        }
    }
    int o=(1<<30);
    while(o>MAX){
        o=o>>1;
    }
    for(int i=1; i<=100; i++)
    {
        if(o==0)break;
        for(int j=0; j<2*n; j++)V[j].clear();
        bool ju=0;
        for(int j=0; j<n; j++)
        {
            for(int k=0; k<n; k++)
            {
                if(j==k)continue;
                int u=(j)*2;
                int v=(k)*2;
                int c=0;
                if(ai[j][k]-o>=0)
                {
                    ju=1;
                    ai[j][k]-=o;
                    c=1;
                }
                if(j%2==0&&k%2==0)
                {
                    if(c==0)
                    {
                        V[u].push_back(v^1);
                        V[v].push_back(u^1);
                    }
                    else
                    {
                        V[u^1].push_back(u);
                        V[v^1].push_back(v);
                    }
                }
                else if(j%2==1&&k%2==1)
                {
                    if(c==0)
                    {
                        V[u].push_back(u^1);
                        V[v].push_back(v^1);
                    }
                    else
                    {
                        V[u^1].push_back(v);
                        V[v^1].push_back(u);
                    }
                }
                else
                {
                    if(c==0)
                    {
                        V[u].push_back(v);
                        V[v].push_back(u);
                        V[u^1].push_back(v^1);
                        V[v^1].push_back(u^1);
                    }
                    else
                    {
                        V[u].push_back(v^1);
                        V[v].push_back(u^1);
                        V[v^1].push_back(u);
                        V[u^1].push_back(v);
                    }
                }
            }
        }
        o=o>>1;
        if(!ju)
        {
            continue;
        }
        indexx=cntnum=0;
        scnt=-1;
        memset(dfn,-1,sizeof(dfn));
        memset(instack,0,sizeof(instack));
        for(int j=0; j<2*n; j++)
        {
            if(dfn[j]==-1)tarjan(j);
        }
        for(int j=0; j<n; j++)
        {
            if(belong[j*2]==belong[j*2+1])
            {
                printf("NO\n");
                return;
            }
        }
    }
    printf("YES\n");
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

题目链接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3273

自从湖南旅游回来之后整个人真的是不佳啊~~~一天就做了这么一个题。。。感觉自己的越来越弱了。。。好了进入正题

分析：首先，这种题先找规律

当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，
则h(1)=1; 
当n=2时，1个根节点固定，还有n-1个节点，可以作为左子树，也可以作为右子树， 即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。这里h(0)表示空，所以只能算一种形态，即h(0)=1; 
当n=3时，1个根节点固定，还有n-1=2个节点，可以在左子树或右子树， 即：h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。 
以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种。
 
即符合Catalan数的定义，可直接利用通项公式得出结果。 递归式： 
  h(n)=h(n-1)*(4*n-2)/(n+1);  该递推关系的解为： 
  h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

然后就啪啪啪、、、Wa了尼玛。。。作为弱者的我不知道怎么错了。。。后来看看递推里面带了除法。。。我去。。。我不会带除法的取余果断百度了一下。。。soga。。看了下要变乘法。。。ok直接套取余模版。。。然后就AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#define LL long long
using namespace std;
const int maxn=123456;
int n,m;
//LL ai[maxn];
int sm[1000],p;//将m分解质因数
int sa[1000];//4*i-2 和 i+1 分解质因数
//素数筛选
int flag[50000],pri[50000],pl;
void prime()
{
    for(int i=2; i<50000; i++)
    {
        if(flag[i]==0) pri[pl++]=i;
        for(int j=0; j<pl&&i*pri[j]<50000; j++)
        {
            flag[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int extgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int r=extgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}
LL over;
void init()
{
    over=1%m;
    LL res=1;//n=1时 sum=1 后面从2开始
    p=0;
    int tm=m;//将m分解质因数
    for(int i=0; pri[i]*pri[i]<=tm; i++)
    {
        if(tm%pri[i]==0)
        {
            sm[p++]=pri[i];
            while(tm%pri[i]==0) tm/=pri[i];
        }
    }
    if(tm>1) sm[p++]=tm;//important
    memset(sa,0,sizeof(sa));
    for(int i=2; i<=n; i++)
    {
        int t;
        t=4*i-2;
        for(int j=0; j<p; j++)
        {
            while(t%sm[j]==0)
            {
                sa[j]++,t/=sm[j];
            }
        }
        res=res*t%m;
        t=i+1;
        for(int j=0; j<p; j++)
        {
            while(t%sm[j]==0)
            {
                sa[j]--,t/=sm[j];
            }
        }
        if(t>1)
        {
            int x,y;
            int r=extgcd(t,m,x,y);
            x=(x%m+m)%m;
            res=res*x%m;
        }
        LL tmp=res;
        for(int j=0; j<p; j++)
        {
            for(int k=0; k<sa[j]; k++)
            {
                tmp=tmp*sm[j]%m;
            }
        }
        over=(over+tmp)%m;
    }
}
void play()
{

    printf("%lld\n",over);
}
int main()
{
    prime();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        init();
        play();
    }
    return 0;
}

题目链接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3374

题意就是说有n棵树，每棵树有个初始值a个金币，而且每过一天会增加b个金币，求m天最多可以得到金币，而且必须每天都要砍一棵树

刚开始以为是贪心。。。Wa，后来举了个反例才发现自己的贪心是错的。。。那么应该怎么做这道题呢？？DP。。。除了贪心我只能想到DP，该怎么DP呢。。。后来想到来个数组dp[i][j]表示前i棵树在j天最大可以产生多少。。。但是有个特别的值。。就是b。。。好像又把我卡住了。。。想一下，就是怎么来确定顺序呢。。。根据b排序。。。把b最小的放前面。。。这样到后面的时候，b已经是最优的了。。。所以这道题的大致感觉就是。当前要放那个哪个地方的话。。。前面的得先放好而且是最优的

 ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a);

这样答案就出来了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=250+10;
struct he
{
    int a,b;
} JLJ[maxn];
int ai[maxn][maxn];
int n,m;
int T;
bool cmp(he a,he b)
{
    return a.b<b.b;
}
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&JLJ[i].a);
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&JLJ[i].b);
    }
}
void play()
{   sort(JLJ+1,JLJ+1+n,cmp);
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {   if(j<=i)
            ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a);
            else break;
        }
    }
    printf("%d\n",ai[n][m]);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1505

题目大意：就是有最多1024个魔法棒放在一排，按照时间顺序对第i个魔法棒改变状态，问最长的连续子序列且都是奇数次改变多长。

题目分析：网上说是暴力。。。我暴力了一发。。。过了。。。但是这题明显是线段树啊，虽然暴力出奇迹。

怎么个线段法？？就是每个区间记录最大值和是否是连续的区间。。怎么定义？？一个节点定义lval，rval，link，max，l,r 其中l，r不用说了，lval就是左边的长度，val同理，max最大值，link是否连续，如果连续，那么lva=rval;如果不连续当然也可能相等，但是不可能是区间的长度，这样我们就好搞了，每次更新子节点，则父节点判断是否连续，如果两个子节点都连续，则父节点lval=左节点的lva+右节点的rval，且max就是当前区间长~~~link当然是连接的啊~~不想等呢》》

那好办了，如果左节点是连得，那父节点lval=左节点lval+右节点lval，且rval=右节点rval，link当然为false了，max就是lmax+rmax

如果右节点是连得，同理哈。。。最后一种情况左右都不连。。。那父节点lval=左节点lval，父节点rval=右节点val，max还是lmax+rmax，link必然false，OK了，讨论完毕。。。AC啦

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=4097;
struct he
{
    int l,r,MAX;
    int lval,rval;
    int link;
} JLJ[maxn*2];
void BuildTree(int l,int r,int now)
{
    JLJ[now].l=l;
    JLJ[now].r=r;
    JLJ[now].link=0;
    JLJ[now].MAX=0;
    JLJ[now].lval=0;
    JLJ[now].rval=0;
    if(l==r)return;
    int mid=(l+r)/2;
    BuildTree(l,mid,now*2);
    BuildTree(mid+1,r,now*2+1);

}
void Update(int l,int now)
{
    if(JLJ[now].l==l&&JLJ[now].r==l)
    {
        if(JLJ[now].MAX==0)JLJ[now].MAX=1;
        else JLJ[now].MAX=0;
        JLJ[now].lval=JLJ[now].rval=JLJ[now].MAX;
        if(JLJ[now].MAX==1)
            JLJ[now].link=1;
        else JLJ[now].link=0;
        return;
    }
    int mid=(JLJ[now].l+JLJ[now].r)/2;
    if(l<=mid)
    {
        Update(l,now*2);
    }
    else
    {
        Update(l,now*2+1);
    }
    int j1=JLJ[now*2].link;
    int j2=JLJ[now*2+1].link;
    if(j1&&j2)
    {
        JLJ[now].link=1;
        JLJ[now].lval=JLJ[now].rval= JLJ[now].MAX=JLJ[now*2].MAX+JLJ[now*2+1].MAX;
    }
    else if(j1)
    {
        JLJ[now].link=0;
        JLJ[now].lval=JLJ[now*2].MAX+JLJ[now*2+1].lval;
        JLJ[now].rval=JLJ[now*2+1].rval;
        JLJ[now].MAX=max(JLJ[now].lval,max(JLJ[now*2+1].MAX,JLJ[now*2].MAX));
    }
    else if(j2)
    {   JLJ[now].link=0;
        JLJ[now].lval=JLJ[now*2].lval;
        JLJ[now].rval=JLJ[now*2].rval+JLJ[now*2+1].MAX;
        JLJ[now].MAX=max(JLJ[now*2].MAX,max(JLJ[now].rval,JLJ[now*2+1].MAX));
    }
    else
    {   JLJ[now].link=0;
        JLJ[now].lval=JLJ[now*2].lval;
        JLJ[now].rval=JLJ[now*2+1].rval;
        JLJ[now].MAX=max(JLJ[now*2].MAX,max(JLJ[now*2+1].MAX,JLJ[now*2].rval+JLJ[now*2+1].lval));
    }
}
int T,n;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        BuildTree(1,4096,1);
        int l;
        int MAX=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&l);
            Update(l,1);
            MAX=max(MAX,JLJ[1].MAX);
        }
        printf("%d\n",MAX);
    }
    //cout << "Hello world!" << endl;
    return 0;
}

问题地址：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4772

题目大意:有一个勇者要去挖宝藏，但是有吸血鬼，且吸血鬼会在m天后出现。。。(就是说勇者最多只能走m步，且最后要在k结束)，

k 是勇者的家。

分析：因为只有n-1条边且连通，所以原图必然是一棵树，所以很典型的想到树形DP

假设从k点到当前点J的深度，既路径长度为len,建立一个数组存放J的子节点的信息。如果J的子节点到J的长度*2+len*2>m直接就跳过。

这里用到背包的思想，因为J可能有很多子节点，所以要选取最优的子节点。。

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
using namespace std;
const int maxn=123;
int n,m,k;
int val[maxn];
int dp[maxn][maxn*2];
vector<pair<int,int> > V[maxn];
void  DFS(int now,int len,int fa)
{
    dp[now][0]=val[now];
    for(int i=0; i<V[now].size(); i++)
    {
        int v=V[now][i].first;
        if(v==fa)continue;
        DFS(v,len+V[now][i].second,now);
        int cd=V[now][i].second*2;
        for(int j=m; j>=0; j--)
        {
            for(int k=0; k<=m; k++)
            {
                if(j+k+cd+len*2>m)break;
                if(dp[v][k]==0)continue;
                dp[now][j+k+cd]=max(dp[now][j]+dp[v][k],dp[now][j+k+cd]);
            }
        }
    }

}
void init()
{
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++)V[i].clear();
    for(int i=1; i<=n; i++)scanf("%d",&val[i]);
    int u,v,w;
    for(int i=1; i<n; i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        V[u].push_back(make_pair(v,w));
        V[v].push_back(make_pair(u,w));
    }
    scanf("%d%d",&k,&m);
}
void play()
{
    DFS(k,0,0);
    int MAX=0;
    for(int i=0; i<=m; i++)
    {
        MAX=max(MAX,dp[k][i]);
    }
    printf("%d\n",MAX);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();

    }
    return 0;
}