#include<bits/stdc++.h>

using namespace std;

typedef long double ld;

const int N=5e5+;

int n,cnt,hd[N],v[N<<],nxt[N<<];

ld ans,p[N],f[N],g[N],w[N<<];

void add(int x,int y,ld z){v[++cnt]=y,nxt[cnt]=hd[x],w[cnt]=z,hd[x]=cnt;}

void dfs1(int u,int fa)

{

    f[u]=p[u];

    for(int i=hd[u];i;i=nxt[i])

    if(v[i]!=fa)dfs1(v[i],u),f[u]=(f[u]+w[i]*f[v[i]]*(-f[u]));

}

void dfs2(int u,int fa,ld p)

{

    g[u]=f[u]+(fabs(-p*f[u])>1e-?p*(g[fa]-p*f[u])/(-p*f[u])*(-f[u]):);

    for(int i=hd[u];i;i=nxt[i])if(v[i]!=fa)dfs2(v[i],u,w[i]);

}

int main()

{

    scanf("%d",&n);

    for(int i=,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z*0.01),add(y,x,z*0.01);

    for(int i=,x;i<=n;i++)scanf("%d",&x),p[i]=x*0.01;

    dfs1(,),dfs2(,,);

    for(int i=;i<=n;i++)ans+=g[i];

    printf("%0.6Lf",ans);

}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,p,a[],f[][][];

int tot,pos;

int main()

{

    int T;cin>>T;

    while(T--)

    {

        cin>>n>>p;

        tot=;

        while(n)a[tot++]=n%p,n/=p;

        tot--;

        memset(f[pos],,sizeof f[pos]);

        f[pos][][]=a[]+,f[pos][][]=p-f[pos][][];

        for(int i=;i<=tot;i++)

        {

            pos^=;

            memset(f[pos],,sizeof f[pos]);

            for(int j=;j<=tot;j++)

            {

                f[pos][j][]+=(a[i]+)*f[pos^][j][]+a[i]*f[pos^][j][];

                f[pos][j+][]+=(p-a[i]-)*f[pos^][j][]+(p-a[i])*f[pos^][j][];

            }

        }

        while(!f[pos][tot][])tot--;

        for(int i=;i<=tot;i++)printf("%lld ",f[pos][i][]);

        puts("");

    }

}

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=1e6+;

int n,a,b,c,q[maxn],qs,qe;

ll s[maxn],f[maxn];

double val(int j,int k)

{return (f[j]-f[k]+a*(s[j]*s[j]-s[k]*s[k])+b*(s[k]-s[j]))*1.0/(*a*(s[j]-s[k]));}

int main()

{

    scanf("%d%d%d%d",&n,&a,&b,&c);

    for(int i=;i<=n;i++)

    {

        int x;

        scanf("%d",&x);

        s[i]=s[i-]+x;

    }

    for(int i=;i<=n;i++)

    {

        while(qs<qe&&val(q[qs+],q[qs])<s[i])

        qs++;

        f[i]=f[q[qs]]+a*(s[i]-s[q[qs]])*(s[i]-s[q[qs]])+b*(s[i]-s[q[qs]])+c;

        while(qs<qe&&val(i,q[qe])<val(q[qe],q[qe-]))

        qe--;

        q[++qe]=i;

    }

    printf("%lld",f[n]);

}

#include<bits/stdc++.h>

using namespace std;

const int N=5e5+;

int n,a[N],ans[][N];

double calc(int u,int v){return sqrt(abs(v-u))+a[u];}

void solve(int l,int r,int ql,int qr,int ans[N])

{

    if(l>r||ql>qr)return;

    int minp=l,mid=ql+qr>>;

    double mn=calc(l,mid),ret=;

    for(int i=l+;i<=r&&i<=mid;i++)

    {

        ret=calc(i,mid);

        if(mn<=ret)mn=ret,minp=i;

    }

    ans[mid]=max(ans[mid],int(ceil(mn))-a[mid]);

    solve(l,minp,ql,mid-,ans),solve(minp,r,mid+,qr,ans);

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    solve(,n,,n,ans[]);

    for(int i=;i<=n/;i++)swap(a[i],a[n-i+]);

    solve(,n,,n,ans[]);

    for(int i=;i<=n;i++)printf("%d\n",max(ans[][i],ans[][n-i+]));

}

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=;

int n,val[N],sum[N],f[N][N],s[N][N];

void solve()

{

    for(int i=;i<=*n;i++)f[i][i]=,s[i][i]=i;

    for(int len=;len<=n;len++)

    for(int i=*n-len;i;i--)

    {

        int j=i+len-;

        f[i][i+len-]=1e9;

        int a=s[i][i+len-],b=s[i+][i+len-],cost=sum[i+len-]-sum[i-];

        for(int k=a;k<=b;k++)

        if(f[i][i+len-]>f[i][k]+f[k+][i+len-]+cost)

        {

            f[i][i+len-]=f[i][k]+f[k+][i+len-]+cost;

            s[i][i+len-]=k;

        }

    }

}

int main()

{

    while(~scanf("%d",&n))

    {

        for(int i=;i<=n;i++)scanf("%d",&val[i]),val[i+n]=val[i];

        for(int i=;i<=*n;i++)sum[i]=sum[i-]+val[i];

        solve();

        int ans=1e9;

        for(int i=;i<=n;i++)ans=min(ans,f[i][i+n-]);

        printf("%d\n",ans);

    }

}

#include<bits/stdc++.h>

using namespace std;

const int mod=,N=3e5;

int n,Q,s,cnt,f[N],sz[N],k[],d[],du[],hd[],v[],nxt[];

int qpow(int a,int b)

{

    int ret=;

    while(b)

    {

        if(b&)ret=1ll*ret*a%mod;

        a=1ll*a*a%mod;b/=;

    }

    return ret;

}

void add(int x,int y){v[++cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt;}

void dfs(int u,int fa,int S)

{

    if(S&(<<u-)){k[u]=d[u]=;return;}

    k[u]=d[u]=du[u];

    for(int i=hd[u];i;i=nxt[i])

    if(v[i]!=fa)

    {

        dfs(v[i],u,S);

        k[u]=(k[u]-k[v[i]])%mod;

        d[u]=(d[u]+d[v[i]])%mod;

    }

    k[u]=qpow(k[u],mod-);

    d[u]=1ll*d[u]*k[u]%mod;

}

int main()

{

    scanf("%d%d%d",&n,&Q,&s);

    for(int i=,x,y;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x),du[x]++,du[y]++;

    for(int i=;i<(<<n);i++)

    dfs(s,,i),f[i]=d[s],sz[i]=sz[i>>]+(i&);

    while(Q--)

    {

        int k,S=;

        scanf("%d",&k);

        for(int i=,x;i<=k;i++)scanf("%d",&x),S|=<<x-;

        int ans=;

        for(int i=S;i;i=(i-)&S)

        ans=(sz[i]&)?(ans+f[i])%mod:(ans-f[i])%mod;

        printf("%d\n",(ans+mod)%mod);

    }

}

#include<bits/stdc++.h>

#define lson l,mid,rt*2

#define rson mid+1,r,rt*2+1

using namespace std;

typedef long long ll;

const int N=2e6+;

struct mat{

    ll f[][];

    mat(){f[][]=f[][]=f[][]=f[][]=;}

    friend mat operator+(mat a,mat b)

    {

        mat c;

        for(int i=;i<;i++)

        for(int j=;j<;j++)

        c.f[i][j]=min(a.f[i][]+min(b.f[][j],b.f[][j]),a.f[i][]+b.f[][j]);

        return c;

    }

}st[N],to;

int n,m,cnt,dep[N],tid[N],bel[N],fa[N],sz[N],son[N],dfn[N],pos[N];

ll p[N],f[N],g[N],cf[N],cg[N];

bool used[N];

vector<int>G[N];

void build(int l,int r,int rt)

{

    used[rt]=bel[tid[l]]==bel[tid[r]];

    if(l==r)return;

    int mid=(l+r)/;

    build(lson);

    build(rson);

}

void modify(int l,int r,int rt,int p)

{

    if(l==r){st[rt]=to;return;}

    int mid=(l+r)/;

    if(p<=mid)modify(lson,p);

    else modify(rson,p);

    if(used[rt])st[rt]=st[rt*]+st[rt*+];

}

mat query(int l,int r,int rt,int L,int R)

{

    if(L==l&&r==R)return st[rt];

    int mid=(l+r)/;

    if(R<=mid)return query(lson,L,R);

    if(L>mid)return query(rson,L,R);

    return query(lson,L,mid)+query(rson,mid+,R);

}

void dfs(int u)

{

    sz[u]=;

    dep[u]=dep[fa[u]]+;

    for(int i=;i<G[u].size();i++)

    if(G[u][i]!=fa[u])

    {

        fa[G[u][i]]=u;

        dfs(G[u][i]);

        sz[u]+=sz[G[u][i]];

        if(sz[G[u][i]]>sz[son[u]])son[u]=G[u][i];

    }

}

void repos(int u)

{

    to.f[][]=cf[u],to.f[][]=cg[u],to.f[][]=to.f[][]=1ll<<;

    modify(,n,,dfn[u]);

}

void dfs(int u,int tp)

{

    bel[u]=tp;

    pos[bel[u]]=dfn[u]=++cnt;

    tid[cnt]=u;

    cf[u]+=p[u];

    f[u]+=p[u];

    if(son[u])dfs(son[u],tp);

    for(int i=;i<G[u].size();i++)

    if(G[u][i]!=fa[u])

    {

        if(G[u][i]!=son[u])dfs(G[u][i],G[u][i]);

        f[u]+=min(f[G[u][i]],g[G[u][i]]);

        g[u]+=f[G[u][i]];

    }

    if(bel[u]==u)cf[fa[u]]+=min(f[u],g[u]),cg[fa[u]]+=f[u];

    repos(u);

}

void update(int x)

{

    while(x)

    {

        int b=bel[x];

        ll mn1=min(f[b],g[b]),mn2=f[b];

        cf[fa[b]]-=mn1;

        cg[fa[b]]-=mn2;

        repos(x);

        mat it=query(,n,,dfn[b],pos[b]);

        f[b]=min(it.f[][],it.f[][]);

        g[b]=min(it.f[][],it.f[][]);

        cf[fa[b]]+=min(f[b],g[b]);

        cg[fa[b]]+=f[b];

        if(f[b]==mn2&&min(f[b],g[b])==mn1)break;

        x=fa[bel[x]];

    }

}

int main()

{

    scanf("%d%d%*s",&n,&m);

    for(int i=;i<=n;i++)scanf("%lld",&p[i]);

    for(int i=,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);

    build(,n,);

    dfs();

    dfs(,);

    build(,n,);

    while(m--)

    {

        int a,x,b,y;

        scanf("%d%d%d%d",&a,&x,&b,&y);

        if((fa[a]==b||fa[b]==a)&&x+y==){puts("-1");continue;}

        (x?cg[a]:cf[a])+=1ll<<,update(a);

        (y?cg[b]:cf[b])+=1ll<<,update(b);

        ll ans=min(cf[],cg[]);

        (x?cg[a]:cf[a])-=1ll<<,update(a);

        (y?cg[b]:cf[b])-=1ll<<,update(b);

        printf("%lld\n",ans);

    }

}

#include<bits/stdc++.h>

using namespace std;

const int N=,mod=;

int n,tot,ans,c[][],fac[N],inv[N],has[N],f[][N][],ch[N][];

struct node{

    int f[][][],cnt;

    node(){memset(f,-,sizeof f),f[][][]=cnt=;}

    bool operator<(const node&x)const

    {

        for(int i=;i<;i++)

        for(int j=;j<;j++)

        for(int k=;k<;k++)

        if(f[i][j][k]!=x.f[i][j][k])return f[i][j][k]<x.f[i][j][k];

        return cnt<x.cnt;

    }

}st[N];

void add(int&a,long long b){a=(a+b)%mod;}

map<node,int>S;

node trans(node u,int x)

{

    node ret;

    ret.cnt=min(u.cnt+(x>=),);

    for(int a=;a<;a++)

    for(int b=;a+b<;b++)

    for(int i=;i<;i++)

    for(int j=;j<;j++)

    for(int k=;k<;k++)

    if(i+j+k+b*<=x&&u.f[a][i][j]!=-)

    ret.f[a+b][j][k]=max(ret.f[a+b][j][k],min(u.f[a][i][j]+i+(x-i-j-k-b*)/,));

    return ret;

}

int dfs(node u)

{

    if(S.count(u))return S[u];

    if(u.cnt==)return ;

    for(int i=;i<;i++)for(int j=;j<;j++)if(u.f[][i][j]==)return ;

    st[++tot]=u,S[u]=tot;

    int pos=tot;

    for(int i=;i<=;i++)ch[pos][i]=dfs(trans(u,i));

    return pos;

}

int main()

{

    scanf("%d",&n);

    for(int i=,x;i<=;i++)scanf("%d%*d",&x),has[x]++;

    for(int i=;i<=;i++)

    {

        c[i][]=;

        for(int j=;j<=i;j++)c[i][j]=c[i-][j-]+c[i-][j];

    }

    fac[]=inv[]=inv[]=;for(int i=;i<=*n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

    for(int i=;i<=*n;i++)fac[i]=1ll*fac[i-]*i%mod,inv[i]=1ll*inv[i-]*inv[i]%mod;

    dfs(node());

    f[][][]=;

    for(int i=;i<=n;i++)

    {

        memset(f[i&],,sizeof f[i&]);

        for(int j=;j<=tot;j++)

        for(int k=has[i];k<=;k++)

        if(ch[j][k])

        for(int t=;t<=(i-)*;t++)

        add(f[i&][ch[j][k]][k+t],1ll*f[i-&][j][t]*c[-has[i]][k-has[i]]);

    }

    for(int i=,sum;i<=n*-;i++)

    {

        sum=;

        for(int j=;j<=tot;j++)add(sum,f[n&][j][i+]);

        add(ans,1ll*sum*fac[i]%mod*fac[*n--i]);

    }

    ans=(1ll*ans*inv[*n-]+)%mod;

    printf("%d",ans);

}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=6e5+;

struct node{int l,r,dis;ll v;}e[N];

int n,m,tot,fa[N],len[N],rt[N],d[N],cnt;

ll p[N],sum;

int merge(int x,int y)

{

    if(!x||!y)return x+y;

    if(e[x].v<e[y].v)swap(x,y);

    e[x].r=merge(e[x].r,y);

    if(e[e[x].l].dis<e[e[x].r].dis)swap(e[x].l,e[x].r);

    if(!e[x].r)e[x].dis=;

    else e[x].dis=e[e[x].r].dis+;

    return x;

}

int pop(int x){return merge(e[x].l,e[x].r);}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n+m;i++)

    {

        scanf("%d%d",&fa[i],&len[i]);

        sum+=len[i],d[fa[i]]++;

    }

    for(int i=n+m;i>;i--)

    {

        ll l=,r=;

        if(i<=n)

        {

            while(--d[i])rt[i]=pop(rt[i]);

            r=e[rt[i]].v,rt[i]=pop(rt[i]);

            l=e[rt[i]].v,rt[i]=pop(rt[i]);

        }

        e[++tot].v=l+len[i];

        e[++tot].v=r+len[i];

        rt[i]=merge(rt[i],merge(tot,tot-));

        rt[fa[i]]=merge(rt[fa[i]],rt[i]);

    }

    while(d[]--)rt[]=pop(rt[]);

    while(rt[])p[++cnt]=e[rt[]].v,rt[]=pop(rt[]);

    for(int i=;i<=cnt;i++)sum-=p[i];

    printf("%lld",sum);

}

#include<bits/stdc++.h>

using namespace std;

const int N=,mod=;

int n,m,ans,p,bin[],w[][],a[][N],f[][N],tot[N],hd[N],nxt[N];

void add(int S,int v)

{

    int u=S%mod;

    for(int i=hd[u];i;i=nxt[i])if(a[p][i]==S){f[p][i]=max(f[p][i],v);return;}

    a[p][++tot[p]]=S,nxt[tot[p]]=hd[u],hd[u]=tot[p],f[p][tot[p]]=v;

}

int main()

{

    scanf("%d%d",&n,&m);

    ans=-1e9;

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    scanf("%d",&w[i][j]);

    bin[]=;for(int i=;i<=;i++)bin[i]=bin[i-]<<;

    tot[p]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=tot[p];j++)a[p][j]<<=;

        for(int j=;j<=m;j++)

        {

            p^=;

            memset(hd,,sizeof hd);

            tot[p]=;

            for(int k=;k<=tot[p^];k++)

            {

                int S=a[p^][k],b1=(S>>j*-)%,b2=(S>>j*)%,val=f[p^][k];

                if(!b1&&!b2)

                {

                    if(i<n&&j<m)add(S+bin[j-]+*bin[j],val+w[i][j]);

                    add(S,val);

                }

                else if(!b1&&b2)

                {

                    if(j<m)add(S,val+w[i][j]);

                    if(i<n)add(S-b2*bin[j]+b2*bin[j-],val+w[i][j]);

                }

                else if(b1&&!b2)

                {

                    if(j<m)add(S-b1*bin[j-]+b1*bin[j],val+w[i][j]);

                    if(i<n)add(S,val+w[i][j]);

                }

                else if(b1==&&b2==)

                {

                    int k1=;

                    for(int t=j+;t<=m;++t)

                    {

                        if((S>>t*)%==)k1++;

                        if((S>>t*)%==)k1--;

                        if(!k1){add(S-bin[j-]-bin[j]-bin[t],val+w[i][j]);break;}

                    }

                }

                else if(b1==&&b2==)

                {

                    int k1=;

                    for(int t=j-;t>=;--t)

                    {

                        if((S>>t*)%==)k1--;

                        if((S>>t*)%==)k1++;

                        if(!k1){add(S-*bin[j-]-*bin[j]+bin[t],val+w[i][j]);break;}

                    }

                }

                else if(b1==&&b2==)add(S-*bin[j-]-bin[j],val+w[i][j]);

                else if(S-bin[j-]-*bin[j]==)ans=max(ans,val+w[i][j]);

            }

        }

    }

    printf("%d",ans);

}

#include<bits/stdc++.h>

using namespace std;

const int N=,mod=1e9+;

int n,m,pw[N],f[N],g[N],h[N],p[N],in[N],ou[N],cnt[N],sz[N];

int main()

{

    scanf("%d%d",&n,&m);

    pw[]=;

    for(int i=;i<=m;++i)pw[i]=2ll*pw[i-]%mod;

    for(int i=,x,y;i<=m;++i)scanf("%d%d",&x,&y),in[<<(--y)]|=<<(--x),ou[<<x]|=<<y;

    sz[]=;

    for(int i=;i<(<<n);++i)sz[i]=sz[i^(i&-i)]+;

    for(int S=;S<(<<n);++S)

    {

        int s=S&-S,T=S^s;

        h[S]=h[T]+sz[in[s]&T]+sz[ou[s]&T],g[S]=,f[S]=pw[h[S]];

        for(int R=T;R;R=(R-)&T)g[S]=(g[S]-1ll*g[R]*f[S^R]%mod+mod)%mod;

        for(int R=S,t;R;R=(R-)&S)

        {

            if(R==S)p[R]=;else t=(R^S)&-(R^S),p[R]=p[R^t]+sz[ou[t]&R]-sz[in[t]&(R^S)];

            f[S]=(f[S]-1ll*pw[p[R]+h[R^S]]*g[R]%mod+mod)%mod;

        }

        g[S]=(g[S]+f[S])%mod;

    }

    printf("%d",f[(<<n)-]);

}