Boleyn Su's Blog

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-25
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
#include <cstring>
using namespace std;

typedef long long int lli;
const int MAXN=12;
const int MAXSTATE=300001;
int N,M;
char map[MAXN][MAXN];
int sc,SC;
int s_[MAXSTATE],S_[MAXSTATE];
lli f_[MAXSTATE],F_[MAXSTATE];
int* s=s_;
int* S=S_;
lli* f=f_;
lli* F=F_;
void qsort(int l,int r)
{
     int i=l,j=r;
     int mid=S[(l+r)>>1];
     while (i<=j)
     {
           while (S[i]<mid) i++;
           while (S[j]>mid) j--;
           if (i<=j)
           {
              int SS;
              lli SF;
              SS=S[i],S[i]=S[j],S[j]=SS,SF=F[i],F[i]=F[j],F[j]=SF;
              i++,j--;
           }
     }
     if (l<j) qsort(l,j);
     if (i<r) qsort(i,r);
}

int main()
{
    cin>>N>>M;
    int lasti=-1,lastj=-1;
    for (int i=0;i<N;i++)
        for (int j=0;j<M;j++)
        {
            cin>>map[i][j];
            if (map[i][j]!='*') lasti=i,lastj=j;
        }
    
    lli answer=0;
    
    SC=0;
    S[SC]=0;
    F[SC]=1;
    SC++;
    for (int i=0;i<N;i++)
    {
        for (int j=0;j<M;j++)
        {
            int* ss;
            lli* sf;
            ss=s,s=S,S=ss,sf=f,f=F,F=sf;
            sc=SC,SC=0;
            
            #define getp(state,p) (((state)>>((p)<<1))&3)
            #define replace(state,p,n) (((state)&(~(3<<((p)<<1))))|n<<((p)<<1))
            #define getl(state) getp(state,j)
            #define getu(state) getp(state,j+1)
            #define replacedr(state,d,r) replace(replace(state,j,d),j+1,r)
            #define getcl(state,p,ns)\
            do\
            {\
              ns=replacedr(state,0,0);\
              int get=2;\
              for (int i=p+2;i<=M;i++)\
              {\
                  if (getp(ns,i)==1) get++;\
                  else if (getp(ns,i)==2) get--;\
                  if (get==1)\
                  {\
                     ns=replace(ns,i,1);\
                     break;\
                  }\
              }\
            }\
            while (false)
            #define getcr(state,p,ns)\
            do\
            {\
              ns=replacedr(state,0,0);\
              int get=2;\
              for (int i=p-1;i>=0;i--)\
              {\
                  if (getp(ns,i)==2) get++;\
                  else if (getp(ns,i)==1) get--;\
                  if (get==1)\
                  {\
                     ns=replace(ns,i,2);\
                     break;\
                  }\
              }\
            }\
            while (false)
            if (map[i][j]=='*')
            {
               for (int si=0;si<sc;si++)
               {
                   int l=getl(s[si]),u=getu(s[si]);
                   if (!(l|u))
                   {
                      int ns;
                      ns=replacedr(s[si],0,0);
                      S[SC]=ns;
                      F[SC]=f[si];
                      SC++;
                   }
               }
            }
            else
            {
                for (int si=0;si<sc;si++)
                {
                    int l=getl(s[si]),u=getu(s[si]);
                    if (l&&u)
                    {
                       int ns;
                       if (l==2&&u==1) ns=replacedr(s[si],0,0);
                       else if (l==1&&u==1) getcl(s[si],j,ns);
                       else if (l==2&&u==2) getcr(s[si],j,ns);
                       else 
                       {
                            
                            if ((!replacedr(s[si],0,0))&&i==lasti&&j==lastj) answer+=f[si];
                            continue;
                       }
                       S[SC]=ns;
                       F[SC]=f[si];
                       SC++;
                    }
                    else if (l)
                    {
                         int ns;
                         ns=replacedr(s[si],l,u);
                         S[SC]=ns;
                         F[SC]=f[si];
                         SC++;
                         ns=replacedr(s[si],u,l);
                         S[SC]=ns;
                         F[SC]=f[si];
                         SC++;
                    }
                    else if (u)
                    {
                         int ns;
                         ns=replacedr(s[si],l,u);
                         S[SC]=ns;
                         F[SC]=f[si];
                         SC++;
                         ns=replacedr(s[si],u,l);
                         S[SC]=ns;
                         F[SC]=f[si];
                         SC++;
                    }
                    else
                    {
                         int ns;
                         /*
                         //there can not be a box without plug
                         ns=replacedr(s[si],0,0);
                         S[SC]=ns;
                         F[SC]=f[si];
                         SC++;
                         */
                         ns=replacedr(s[si],1,2);
                         S[SC]=ns;
                         F[SC]=f[si];
                         SC++;
                    }
                }
            }
            {
                qsort(0,SC-1);
                int RSC=0;
                int i=0;
                while (i<SC)
                {
                      int j=i+1;
                      while (j<SC&&S[i]==S[j]) F[i]+=F[j],j++;
                      S[RSC]=S[i];
                      F[RSC++]=F[i];
                      i=j;
                }
                SC=RSC;
            }
        }
        {
            int RSC=0;
            int i=0;
            while (i<SC)
            {
                  while (i<SC&&getp(S[i],M)) i++;
                  if (i<SC) S[RSC]=S[i]<<(1<<1),F[RSC++]=F[i++];
            }
            SC=RSC;
        }
    }
    cout<<answer<<endl;
}

CODE:

#include <iostream>
using namespace std;

int N;
int adjs[100+1];
int adj[100+1][100];
int BLACKS;
int color[100+1];
void dfs(int u,int c)
{
     if (!color[u])
     {
        color[u]=c;
        if (c==1) BLACKS++;
        for (int e=0;e<adjs[u];e++)
            dfs(adj[u][e],-c);
     }
}

int main()
{
    cin>>N;
    for (int i=1;i<=N;i++)
    {
        for (;;)
        {
            cin>>adj[i][adjs[i]];
            if (adj[i][adjs[i]]) adjs[i]++;
            else break;
        }
    }
    for (int i=1;i<=N;i++) dfs(i,1);
    cout<<BLACKS<<endl;
    for (int i=0,j=0;i<BLACKS;i++)
    {
        while (color[++j]!=1) ;
        cout<<j<<char(i==BLACKS?'\n':' ');
    }
    return 0;
}

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-22
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

#define end first
#define begin second
#define segment first
#define id second
typedef pair<double,double> segment;
typedef pair<segment,int> segment_with_id;

int N;
segment_with_id one[10000+1];
double t[2][10000+1];
int rid[10000+1];
int d2ic;
pair<int,int> d2i[20000+2];
int tidc;
int tid[2][10000+1];
double i2d[20000+2];
double f[10000+1];
int pre[10000+1];
int best_id;
int st1[(20000+2)*4];
int st2[(20000+2)*4];
int answerc;
int answer[10000+1];

bool sort_rule(const pair<int,int>& a,const pair<int,int>& b)
{
    return t[a.first][a.second]<t[b.first][b.second];
}
void insert1(int L,int R,int p,int v,int root=1)
{
    if (L<=p&&p<=R)
    {
        if (f[st1[root]]<f[v])
            st1[root]=v;
        if (L==R) return;
        int LL=L,LR=(L+R)>>1,Lroot=root<<1;
        int RL=LR+1,RR=R,Rroot=Lroot|1;
        insert1(LL,LR,p,v,Lroot);
        insert1(RL,RR,p,v,Rroot);
    }
}
int query1(int L,int R,int p,int root=1)
{
    if (p<L) return 0;
    else if (R<=p) return st1[root];
    else
    {
        int LL=L,LR=(L+R)>>1,Lroot=root<<1;
        int RL=LR+1,RR=R,Rroot=Lroot|1;
        int a=query1(LL,LR,p,Lroot),b=query1(RL,RR,p,Rroot);
        return f[a]>f[b]?a:b;
    }
}
void insert2(int L,int R,int p,int v,int root=1)
{
    if (L<=p&&p<=R)
    {
        if (f[st2[root]]-i2d[tid[1][st2[root]]]*2.0<f[v]-i2d[tid[1][v]]*2.0)
            st2[root]=v;
        if (L==R) return;
        int LL=L,LR=(L+R)>>1,Lroot=root<<1;
        int RL=LR+1,RR=R,Rroot=Lroot|1;
        insert2(LL,LR,p,v,Lroot);
        insert2(RL,RR,p,v,Rroot);
    }
}
int query2(int L,int R,int p,int root=1)
{
    if (R<p) return 0;
    else if (p<=L) return st2[root];
    else
    {
        int LL=L,LR=(L+R)>>1,Lroot=root<<1;
        int RL=LR+1,RR=R,Rroot=Lroot|1;
        int a=query2(LL,LR,p,Lroot),b=query2(RL,RR,p,Rroot);
        return f[a]-i2d[tid[1][a]]*2.0>f[b]-i2d[tid[1][b]]*2.0?a:b;
    }
}

int main()
{
    cin>>t[0][0]>>t[1][0]
       >>N;
    d2i[d2ic++]=make_pair(0,0),
    d2i[d2ic++]=make_pair(1,0);
    for (int i=1;i<=N;i++)
    {
        cin>>one[i].segment.begin>>one[i].segment.end;
        one[i].id=i;
    }
    sort(one+1,one+N+1);
    for (int i=1;i<=N;i++)
    {
        t[0][i]=one[i].segment.begin,
        t[1][i]=one[i].segment.end;
        rid[i]=one[i].id;
        d2i[d2ic++]=make_pair(0,i),
        d2i[d2ic++]=make_pair(1,i);
    }
    sort(d2i,d2i+d2ic,sort_rule);
    for (int i=0;i<d2ic;i++)
    {
        if (i&&t[d2i[i].first][d2i[i].second]!=t[d2i[i-1].first][d2i[i-1].second]) tidc++;
        tid[d2i[i].first][d2i[i].second]=tidc;
        i2d[tidc]=t[d2i[i].first][d2i[i].second];
    }
    f[best_id=0]=0;
    for (int i=1;i<=N;i++)
    {
        int npre;
        double nf;
        npre=0;
        nf=i2d[tid[1][i]]-i2d[tid[0][i]];
        if (nf>f[i])
        {
            pre[i]=npre;
            f[i]=nf;
        }
        npre=query1(0,tidc,tid[0][i]);
        nf=i2d[tid[1][i]]-i2d[tid[0][i]]+f[npre];
        if (nf>f[i])
        {
            pre[i]=npre;
            f[i]=nf;
        }
        npre=query2(0,tidc,tid[0][i]);
        nf=f[npre]-i2d[tid[1][npre]]*2.0+i2d[tid[0][i]]+i2d[tid[1][i]];
        if (nf>f[i])
        {
            pre[i]=npre;
            f[i]=nf;
        }
        if (f[i]>f[best_id]) best_id=i;
        insert1(0,tidc,tid[1][i],i);
        insert2(0,tidc,tid[1][i],i);
    }
    if (f[best_id]>=(i2d[tid[1][0]]-i2d[tid[0][0]])*2.0/3.0)
    {
        answer[answerc=1]=best_id;
        while (pre[answer[answerc]])
        {
            answer[answerc+1]=pre[answer[answerc]];
            answerc++;
        }
        cout<<answerc<<endl;
        for (int i=1;i<=answerc;i++)
            cout<<rid[answer[i]]<<endl;
    }
    else cout<<0<<endl;
    return 0;
}

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-18
DESCRIPTION:
$DESCRIPTION
*/

import java.io.*;
import java.util.*;

public class Ural {
    public static void main(String args[])
    {
        new Ural();
    }
    public int c2i(char c)
    {
        if ('A'<=c&&c<='Z') return (int)(c-'A')+10;
        else return (int)(c-'0');
    }
    public Ural()
    {
        Scanner cin=new Scanner(new BufferedInputStream(System.in));
        String s=cin.nextLine();
        int sum=0;
        int mink=2;
        for (int i=0;i<s.length();i++)
        {
            sum+=c2i(s.charAt(i));
            if (c2i(s.charAt(i))>=mink) mink=c2i(s.charAt(i))+1;
        }
        for (int k=mink;k<=36;k++)
        {
            if (sum%(k-1)==0)
            {
                System.out.println(k);
                return;
            }
        }
        System.out.println("No solution.");
    }
}

CODE:

import java.io.*;
import java.util.*;
import java.math.*;

public class Ural {
    public static void main(String args[]) throws IOException
    {
        new Ural();
    }
    public int N;
    public BigInteger x[],y[],ax,ay,bx,by,cx,cy;
    public BigInteger cross(BigInteger ax,BigInteger ay,BigInteger bx,BigInteger by,BigInteger cx,BigInteger cy)
    {
        return bx.subtract(ax).multiply(cy.subtract(ay)).subtract(by.subtract(ay).multiply(cx.subtract(ax)));
    }
    public BigInteger dot(BigInteger ax,BigInteger ay,BigInteger bx,BigInteger by,BigInteger cx,BigInteger cy)
    {
        return bx.subtract(ax).multiply(cx.subtract(ax)).add(by.subtract(ay).multiply(cy.subtract(ay)));
    }
    public boolean less(BigInteger xa,BigInteger ya,BigInteger xb,BigInteger yb)
    {
        BigInteger A=BigInteger.valueOf(dot(xa,ya,ax,ay,bx,by).signum()).multiply(dot(xa,ya,ax,ay,bx,by).pow(2).multiply(dot(xb,yb,ax,ay,ax,ay).multiply(dot(xb,yb,bx,by,bx,by))));
        BigInteger B=BigInteger.valueOf(dot(xb,yb,ax,ay,bx,by).signum()).multiply(dot(xb,yb,ax,ay,bx,by).pow(2).multiply(dot(xa,ya,ax,ay,ax,ay).multiply(dot(xa,ya,bx,by,bx,by))));
        return A.compareTo(B)<0;
    }
    public void nth_element(int l,int r,int n)
    {
        int i=l,j=r;
        BigInteger midx=x[(l+r)/2];
        BigInteger midy=y[(l+r)/2];
        while (i<=j)
        {
            while (less(x[i],y[i],midx,midy)) i++;
            while (less(midx,midy,x[j],y[j])) j--;
            if (i<=j)
            {
                BigInteger swap;
                swap=x[i];
                x[i]=x[j];
                x[j]=swap;
                swap=y[i];
                y[i]=y[j];
                y[j]=swap;
                i++;
                j--;
            }
        }
        if (l<j)
        {
            if (n<=j) nth_element(l,j,n);
        }
        if (i<r)
        {
            nth_element(i,r,n-i);
        }
    }
    public Ural()
    {
        Scanner cin=new Scanner(new BufferedInputStream(System.in));
        N=cin.nextInt();
        if (N%2!=1)
        {
            System.out.println("No solution");
            return ;
        }
        x=new BigInteger[N];
        y=new BigInteger[N];
        for (int i=0;i<N;i++)
        {
            x[i]=cin.nextBigInteger();
            y[i]=cin.nextBigInteger();
        }
        int ai,bi,ci;
        ax=x[0];
        ay=y[0];
        ai=0;
        for (int i=1;i<N;i++)
            if (x[i].compareTo(ax)>0)
            {
                ax=x[i];
                ay=y[i];
                ai=i;
            }
        N--;
        x[ai]=x[N];
        y[ai]=y[N];
        System.out.println(ax+" "+ay);
        bx=x[0];
        by=y[0];
        bi=0;
        for (int i=1;i<N;i++)
            if (cross(ax,ay,bx,by,x[i],y[i]).compareTo(BigInteger.valueOf(0))>0)
            {
                bx=x[i];
                by=y[i];
                bi=i;
            }
        N--;
        x[bi]=x[N];
        y[bi]=y[N];
        System.out.println(bx+" "+by);
        nth_element(0,N-1,N/2);
        cx=x[N/2];
        cy=y[N/2];
        System.out.println(cx+" "+cy);
    }
}

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-17
DESCRIPTION:
$DESCRIPTION
*/
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXS=10000000+1;
const int MAXM=6;
int N;
bool f[MAXS];
int sl;
char s[MAXS];
char match[MAXM][7]={"out","output","puton","in","input","one"};
int matchl[MAXM]={3,6,5,2,5,3};

int main()
{
    gets(s);
    sscanf(s,"%d",&N);
    for (int n=0;n<N;n++)
    {
        gets(s);
        sl=strlen(s);
        memset(f,0,sizeof(f));
        f[0]=true;
        for (int i=0;i<sl;i++)
            if (f[i])
                for (int j=0;j<MAXM;j++)
                    if (i+matchl[j]<=sl)
                    {
                        bool matched=true;
                        for (int k=0;k<matchl[j];k++)
                            if (s[i+k]!=match[j][k])
                                matched=false;
                        if (matched) f[i+matchl[j]]=true;
                    }
        if (f[sl]) puts("YES");
        else puts("NO");
    }
    return 0;
}

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-17
DESCRIPTION:
$DESCRIPTION
*/

import java.io.*;
import java.util.*;

public class Ural {
    public static void main(String args[])
    {
        new Ural();
    }
    public String exp;
    public int N,M,K;
    public int mx[],my[],kx[],ky[],iv[];
    public boolean vars[];
    public final int DIRS=4;
    public int dir,x,y;
    public int dx[],dy[];
    public int getid(char ch)
    {
        return (int)(ch-'A');
    }
    public boolean calc()
    {
        Stack<Boolean> va=new Stack<Boolean>();
        Stack<Character> op=new Stack<Character>();
        for (int i=0;i<exp.length();i++)
        {
            boolean opn1,opn2;
            switch (exp.charAt(i))
            {
                case '!':
                    op.push('!');
                    break;
                case '&':
                    while (!op.empty())
                    {
                        if (op.peek()=='!')
                        {
                            opn1=va.pop();
                            va.push(!opn1);
                        }
                        else if (op.peek()=='&')
                        {
                            opn1=va.pop();
                            opn2=va.pop();
                            va.push(opn1&&opn2);
                        }
                        else break;
                        op.pop();
                    }
                    op.push('&');
                    break;
                case '|':
                    while (!op.empty())
                    {
                        if (op.peek()=='!')
                        {
                            opn1=va.pop();
                            va.push(!opn1);
                        }
                        else if (op.peek()=='&')
                        {
                            opn1=va.pop();
                            opn2=va.pop();
                            va.push(opn1&&opn2);
                        }
                        else if (op.peek()=='|')
                        {
                            opn1=va.pop();
                            opn2=va.pop();
                            va.push(opn1||opn2);
                        }
                        else break;
                        op.pop();
                    }
                    op.push('|');
                    break;
                case '(':
                    op.push('(');
                    break;
                case ')':
                    while (op.peek()!='(')
                    {
                        if (op.peek()=='!')
                        {
                            opn1=va.pop();
                            va.push(!opn1);
                        }
                        else if (op.peek()=='&')
                        {
                            opn1=va.pop();
                            opn2=va.pop();
                            va.push(opn1&&opn2);
                        }
                        else if (op.peek()=='|')
                        {
                            opn1=va.pop();
                            opn2=va.pop();
                            va.push(opn1||opn2);
                        }
                        else break;
                        op.pop();
                    }
                    op.pop();
                    break;
                case '0':
                    va.push(false);
                    break;
                case '1':
                    va.push(true);
                    break;
                default:
                    va.push(vars[getid(exp.charAt(i))]);
                    break;
            }
        }
        return va.pop();
    }
    public Ural()
    {
        Scanner cin=new Scanner(new BufferedInputStream(System.in));
        exp=cin.nextLine();
        N=cin.nextInt();
        M=cin.nextInt();
        K=cin.nextInt();
        mx=new int[M];
        my=new int[M];
        kx=new int[K];
        ky=new int[K];
        iv=new int[K];
        for (int i=0;i<M;i++)
        {
            mx[i]=cin.nextInt();
            my[i]=cin.nextInt();
        }
        for (int i=0;i<K;i++)
        {
            kx[i]=cin.nextInt();
            ky[i]=cin.nextInt();
            iv[i]=getid(cin.next().charAt(0));
        }
        exp=exp.replaceAll("NOT","!");
        exp=exp.replaceAll("AND","&");
        exp=exp.replaceAll("OR","|");
        exp=exp.replaceAll("TRUE","1");
        exp=exp.replaceAll("FALSE","0");
        exp=exp.replaceAll(" ","");
        exp="("+exp+")";
        vars=new boolean[26];
        Arrays.fill(vars,false);
        dir=0;
        x=0;
        y=0;
        dx=new int[]{1,0,-1,0};
        dy=new int[]{0,1,0,-1};
        while (Math.abs(x)<=N&&Math.abs(y)<=N)
        {
            System.out.println(x+" "+y);
            for (int i=0;i<M;i++)
                if (mx[i]==x&&my[i]==y)
                {
                    if (calc())
                    {
                        if (dir==0) dir+=DIRS;
                        dir--;
                    }
                    else
                    {
                        dir++;
                        if (dir==DIRS) dir-=DIRS;
                    }
                }
            for (int i=0;i<K;i++)
                if (kx[i]==x&&ky[i]==y)
                    vars[iv[i]]=!vars[iv[i]];
            x+=dx[dir];
            y+=dy[dir];
        }
    }
}

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-11
DESCRIPTION:
$DESCRIPTION
*/

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[])
    {
        new Main();
    }
    public int N,M;
    public String message[],mask[],words[];
    public String get_answer()
    {
        StringBuffer masks[][]=new StringBuffer[4][N];
        for (int i=0;i<N;i++)
            masks[0][i]=new StringBuffer(mask[i]);
        for (int i=1;i<4;i++)
            for (int x=0;x<N;x++)
            {
                masks[i][x]=new StringBuffer();
                masks[i][x].setLength(N);
                for (int y=0;y<N;y++)
                    masks[i][x].setCharAt(y,masks[i-1][N-1-y].charAt(x));
            }
        StringBuffer answers_[]=new StringBuffer[4];
        for (int start=0;start<4;start++)
        {
            answers_[start]=new StringBuffer();
            for (int offset=0;offset<4;offset++)
            {
                int now=(start+offset)%4;
                for (int x=0;x<N;x++)
                    for (int y=0;y<N;y++)
                        if (masks[now][x].charAt(y)=='*')
                        {
                            char get=message[x].charAt(y);
                            if (get=='.')
                            {
                                if (answers_[start].length()!=0&&answers_[start].charAt(answers_[start].length()-1)!=' ')
                                    answers_[start].append(' ');
                            }
                            else answers_[start].append(get);
                        }
            }
            while (answers_[start].length()!=0&&answers_[start].charAt(answers_[start].length()-1)==' ')
                answers_[start].deleteCharAt(answers_[start].length()-1);
        }
        String answers[]=new String[4];
        for (int i=0;i<4;i++) answers[i]=new String(answers_[i]);
        Arrays.sort(answers);
        for (int start=0;start<4;start++)
        {
            String set[]=answers[start].split(" ");
            boolean possible=true;
            for (int i=0;i<set.length;i++)
            {
                boolean possible_=false;
                for (int j=0;j<M;j++)
                {
                    if (set[i].equals(words[j])) possible_=true;
                }
                if (!possible_)
                {
                    possible=false;
                    break;
                }
            }
            if (possible) return answers[start];
        }
        return "FAIL TO DECRYPT";
    }
    public Main()
    {
        Scanner cin=new Scanner(new BufferedInputStream(System.in));
        int T=cin.nextInt();
        for (int t=1;t<=T;t++)
        {
            N=cin.nextInt();
            message=new String[N];
            mask=new String[N];
            cin.nextLine();
            for (int i=0;i<N;i++)
                message[i]=cin.nextLine();
            for (int i=0;i<N;i++)
                mask[i]=cin.nextLine();
            M=cin.nextInt();
            cin.nextLine();
            words=new String[M];
            for (int i=0;i<M;i++)
                words[i]=cin.nextLine();
            System.out.println("Case #"+t+": "+get_answer());
        }
    }
}

2011年成都赛区H题的题解。

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-11
DESCRIPTION:
$DESCRIPTION
*/

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[])
    {
        new Main();
    }
    public class Graph {
        public class edge {
            public int v,d,n;
        }
        public int top;
        public edge edges[];
        public int adj[];
        public int N;
        public Graph(int N_)
        {
            N=N_;
            edges=new edge[(N-1)*2];
            top=0;
            adj=new int[N];
            Arrays.fill(adj,-1);
        }
        void add_edge(int u,int v,int d)
        {
            u--;v--;
            edges[top]=new edge();edges[top].v=v;edges[top].d=d;edges[top].n=adj[u];adj[u]=top++;
            edges[top]=new edge();edges[top].v=u;edges[top].d=d;edges[top].n=adj[v];adj[v]=top++;
        }
    }
    public Graph graph;
    public long get_answer()
    {
        int qh,qt;
        int q[]=new int[graph.N];
        int f[]=new int[graph.N];
        int d[]=new int[graph.N];
        boolean inq[]=new boolean[graph.N];
        Arrays.fill(inq,false);
        inq[q[qh=qt=0]=0]=true;
        while (qh<=qt)
        {
            int u=q[qh++];
            for (int e=graph.adj[u];e!=-1;e=graph.edges[e].n)
            {
                int v=graph.edges[e].v;
                if (!inq[v])
                {
                    inq[q[++qt]=v]=true;
                    f[v]=u;
                    d[v]=graph.edges[e].d;
                }
            }
        }
        long answer=0;
        int c[]=new int[graph.N];
        Arrays.fill(c,0);
        while (qt>=0)
        {
            int u=q[qt--];
            c[u]++;
            c[f[u]]+=c[u];
            answer+=(long)(Math.min(c[u],graph.N-c[u]))*(long)(d[u])*(long)(2);
        }
        return answer;
    }
    public Main()
    {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int T=cin.nextInt();
        for (int t=1;t<=T;t++)
        {
            int N=cin.nextInt();
            graph=new Graph(N);
            for (int i=1;i<N;i++)
            {
                int X,Y,Z;
                X=cin.nextInt();
                Y=cin.nextInt();
                Z=cin.nextInt();
                graph.add_edge(X,Y,Z);
            }
            System.out.println("Case #"+t+": "+get_answer());
        }
    }
}