A1471

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll s[100001][10],cnt;
bool f[100001];
bool insert(string x){
	ll len=x.length();
	ll now=0;
	bool flag=true;
	for(ll i=0;i<len;i++){
		if(s[now][x[i]-'0']==0){
			flag=false;
			s[now][x[i]-'0']=++cnt;
		}
		now=s[now][x[i]-'0'];
		if(f[now]) return true;
	}
	f[now]=true;
	return flag;
}
int main(){
	ll t;
	cin>>t;
	while(t--){
		cnt=0;
		ll n;
		cin>>n;
		for(ll i=0;i<=100000;i++) f[i]=false;
		for(ll i=0;i<=100000;i++) for(ll j=0;j<=9;j++) s[i][j]=0;
		bool flag=false;
		for(ll i=1;i<=n;i++){
			string x;
			cin>>x;
			if(flag) continue;
			flag=insert(x);
		}
		if(flag) cout<<"NO\n";
		else cout<<"YES\n";
	}
	return 0;
}

A1472

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,cnt;
ll st[33],s[3200001][2];
ll insert(){
	ll ret=0,now=0;
	for(ll i=1;i<=32;i++){
		if(s[now][!st[i]]){
			now=s[now][!st[i]];
			ret=ret*2+1;
		}
		else if(s[now][st[i]]){
			now=s[now][st[i]];
			ret*=2;
		}
		else break;
	}
	now=0;
	for(ll i=1;i<=32;i++){
		if(s[now][st[i]]==0){
			s[now][st[i]]=++cnt;
		}
		now=s[now][st[i]];
	}
	return ret;
}
int main(){
	scanf("%lld",&n);
	ll ans=-1;
	for(ll i=1;i<=n;i++){
		ll x;
		scanf("%lld",&x);
		for(ll i=1;i<=32;i++){
			st[32-i+1]=x%2;
			x/=2;
		}
		ans=max(ans,insert());
	}
	printf("%lld",ans);
	return 0;
}

A1473

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,cnt;
ll st[33],s[6000005][2];
ll a[400005],b[400005],l[400005],r[400005];
ll insert(){
	ll ret=0,now=0;
	for(ll i=1;i<=32;i++){
//		cout<<now<<" "<<st[i]<<" "<<s[now][st[i]]<<" "<<s[now][!st[i]]<<endl;
		if(s[now][!st[i]]){
			now=s[now][!st[i]];
			ret=ret*2+1;
		}
		else if(s[now][st[i]]){
			now=s[now][st[i]];
			ret*=2;
		}
		else break;
	}
	now=0;
	for(ll i=1;i<=32;i++){
		if(s[now][st[i]]==0){
			s[now][st[i]]=++cnt;
		}
		now=s[now][st[i]];
	}
	return ret;
}
int main(){
	scanf("%lld",&n);
	ll ans=-1;
	for(ll i=1;i<=n;i++){
		ll x;
		scanf("%lld",&x);
		a[i]=a[i-1]^x;
	}
	for(ll i=1;i<=n;i++){
		b[i]=a[n]^a[i-1];
	}
	for(ll i=1;i<=n;i++){
		ll x=a[i];
		for(ll j=1;j<=32;j++){
			st[32-j+1]=x%2;
			x/=2;
		}
		l[i]=max(l[i-1],insert());
	}
	for(ll i=1;i<=6000001;i++) s[i][0]=s[i][1]=0;
	cnt=0;
	for(ll i=n;i>=1;i--){
		ll x=b[i];
		for(ll j=1;j<=32;j++){
			st[32-j+1]=x%2;
			x/=2;
		}
		r[i]=max(r[i+1],insert());
	}
//	for(ll i=1;i<=n;i++) cout<<a[i]<<" "<<b[i]<<endl;
	for(ll i=1;i<n;i++) ans=max(ans,l[i]+r[i+1]);
	printf("%lld",ans);
	return 0;
}

A1474

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll s[101][10],cnt;
string x;
bool vis[101];
bool insert(){
	ll len=x.length(),now=0;
	bool flag=true;
	for(ll i=0;i<len;i++){
		if(s[now][x[i]-'0']==0){
			s[now][x[i]-'0']=++cnt;
			flag=false;
		}
//		cout<<now<<" ";
		now=s[now][x[i]-'0'];
		if(vis[now]){
//			cout<<"!!! "<<x<<" "<<i<<endl;
			return true;
		}
	}
	vis[now]=true;
//	cout<<now<<endl;
//	if(flag) cout<<"!!! "<<x<<endl;
	return flag;
}
int main(){
	ll t=1;
	bool flag=false;
	while(cin>>x){
		if(x!="9"){
			if(flag) continue;
			flag=insert();
		}
		else{
			if(flag) printf("Set %lld is not immediately decodable\n",t);
			else printf("Set %lld is immediately decodable\n",t);
			t++;
			for(ll i=0;i<=100;i++){
				for(ll j=0;j<=9;j++) s[i][j]=0;
				vis[i]=false;
			}
			cnt=0;
			flag=false;
		}
	}
}

A1475

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,cnt;
ll s[501][27];
bool vis[501];
void insert(string x){
	ll len=x.length(),now=0;
	for(ll i=0;i<len;i++){
		if(s[now][x[i]-'a']==0){
			s[now][x[i]-'a']=++cnt;
		}
		now=s[now][x[i]-'a'];
	}
	vis[now]=true;
}
ll rem[1051001];
bool viis[1051001];
string sx;
ll dfs(ll h){
	if(viis[h]) return rem[h];
	ll now=0,hh=0;
	ll ret=0;
	while(h+hh<(ll)(sx.length())){
		if(s[now][sx[h+hh]-'a']==0) break;
		now=s[now][sx[h+hh]-'a'];
		hh++;
		if(vis[now]){
			ret=max(ret,hh+dfs(h+hh));
		}
	}
	rem[h]=ret;
	viis[h]=true;
	return ret;
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		string x;
		cin>>x;
		insert(x);
	}
	for(ll i=1;i<=m;i++){
		cin>>sx;
		for(ll i=0;i<=1051000;i++){
			viis[i]=false;
			rem[i]=0;
		}
		ll ans=dfs(0);
		cout<<ans<<endl;
	}
	return 0;
}

A1476

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,cnt;
ll x[10001],s[1000001][2],siize[1000001];
ll vis[1000001];
void insert(ll len){
	ll now=0;
	for(ll i=1;i<=len;i++){
		if(s[now][x[i]]==0) s[now][x[i]]=++cnt;
		now=s[now][x[i]];
	}
	vis[now]++;
}
void init(ll h){
	siize[h]=vis[h];
	if(s[h][1]){
		init(s[h][1]);
		siize[h]+=siize[s[h][1]];
	}
	if(s[h][0]){
		init(s[h][0]);
		siize[h]+=siize[s[h][0]];
	}
}
ll check(ll len){
	ll now=0,ret=0;
	for(ll i=1;i<=len;i++){
		if(s[now][x[i]]==0) return ret;
		now=s[now][x[i]];
		ret+=vis[now];
	}
	ret+=siize[now]-vis[now];
	return ret;
}
int main(){
	scanf("%lld %lld",&n,&m);
	for(ll i=1;i<=n;i++){
		ll len;
		scanf("%lld",&len);
		for(ll i=1;i<=len;i++) scanf("%lld",&x[i]);
		insert(len);
	}
	init(0);
	for(ll i=1;i<=m;i++){
		ll len;
		scanf("%lld",&len);
		for(ll i=1;i<=len;i++) scanf("%lld",&x[i]);
		ll ans=check(len);
		printf("%lld\n",ans);
	}
	return 0;
}

A1477

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string str[100100],s2[100100];
queue<ll> q;
ll ans[100100],s[510100][26],cnt,vis[510100],siize[510010];
ll insert(string x,ll yy){
	ll len=x.length(),now=0,ret=yy;
	for(ll i=1;i<=len;i++){
		if(s[now][x[i-1]-'a']==0) s[now][x[i-1]-'a']=++cnt;
		now=s[now][x[i-1]-'a'];
		ret=min(ret,yy-vis[now]);
	}
	vis[now]=yy;
	return ret;
}
void insert2(string x,ll yy){
	ll len=x.length(),now=0;
	for(ll i=1;i<=len;i++){
		if(s[now][x[i-1]-'a']==0) s[now][x[i-1]-'a']=++cnt;
		now=s[now][x[i-1]-'a'];
	}
	vis[now]=yy;
}
void dfs(ll p){
	siize[p]=(vis[p]>0);
	for(ll i=0;i<26;i++) if(s[p][i]!=0){
		dfs(s[p][i]);
		siize[p]+=siize[s[p][i]];
	}
}
struct node{
	ll x,num;
};
bool cmp(node aa,node bb){
	if(aa.num==0) return false;
	if(aa.num!=bb.num) return aa.num<bb.num;
	return aa.x<bb.x;
}
ll did(ll p,int *f){
	int f2[100001];
	ll cntt=0,cnttt=0;
	for(ll i=0;i<26;i++){
		if(s[p][i]==0) continue;
		if(vis[s[p][i]]) f[++cntt]=s[p][i];
		else cnttt+=did(s[p][i],&f2[cnttt]);
	}
	for(ll i=cntt+1;i<=cntt+cnttt;i++){
		f[i]=f2[i-cntt];
	}
	return cntt+cnttt;
}
void init(ll p){
	if(vis[p]) q.push(vis[p]);
	ll nuum=26;
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > gt;
	for(ll i=0;i<26;i++){
		if(s[p][i]==0){
			nuum--;
			continue;
		}
		if(vis[s[p][i]]==0){
			nuum--;
			int f[100001];
			ll len=did(s[p][i],&f[0]);
			for(ll i=1;i<=len;i++){
				gt.push(make_pair(siize[f[i]],f[i]));
				nuum++;
			}
		} 
		else{
			gt.push(make_pair(siize[s[p][i]],s[p][i]));
		}
	}
	while(!gt.empty()){
		init(gt.top().second);
		gt.pop();
	}
}
int main(){
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>str[i];
		ll len=str[i].length();
		for(ll j=1;j*2<=len;j++) swap(str[i][j-1],str[i][len-j]);
	}
	for(ll i=1;i<=n;i++){
		insert2(str[i],i);
	}
	dfs(0);
	init(0);
	for(ll i=0;i<=510099;i++){
		for(ll j=0;j<26;j++) s[i][j]=0;
		vis[i]=0;
	}
	cnt=0;
	swap(s2,str);
	ll cnt2=0;
	while(!q.empty()){
		str[++cnt2]=s2[q.front()];
		q.pop();
	}
	for(ll i=1;i<=n;i++){
		ans[i]=insert(str[i],i);
	}
	ll rans=0;
	for(ll i=1;i<=n;i++) rans+=ans[i];
	cout<<rans;
	return 0;
}

A1478

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
	ll to,next,w;
}e[100001];
ll n,cnt,home[100001],v[100001],s[3200001][2];
void add(ll a,ll b,ll c){
	e[++cnt].to=b;
	e[cnt].next=home[a];
	e[cnt].w=c;
	home[a]=cnt;
}
void dfs(ll p,ll fa,ll val){
	v[p]=v[fa]^val;
	for(ll i=home[p];i;i=e[i].next){
		ll t=e[i].to;
		dfs(t,p,e[i].w);
	}
}
ll insert(ll p){
	ll x[33];
	for(ll i=32;i>=1;i--){
		x[i]=p%2;
		p/=2;
	}
	ll now=0,ret=0;
	for(ll i=1;i<=32;i++){
		if(s[now][1-x[i]]){
			now=s[now][1-x[i]];
			ret=ret*2+1;
		}
		else if(s[now][x[i]]){
			now=s[now][x[i]];
			ret*=2;
		}
		else break;
	}
	now=0;
	for(ll i=1;i<=32;i++){
		if(s[now][x[i]]==0) s[now][x[i]]=++cnt;
		now=s[now][x[i]];
	}
	return ret;
}
/*ll insert(ll p){
	ll ret=0,now=0;
	ll st[]
	for(ll i=1;i<=32;i++){
		if(s[now][!st[i]]){
			now=s[now][!st[i]];
			ret=ret*2+1;
		}
		else if(s[now][st[i]]){
			now=s[now][st[i]];
			ret*=2;
		}
		else break;
	}
	now=0;
	for(ll i=1;i<=32;i++){
		if(s[now][st[i]]==0){
			s[now][st[i]]=++cnt;
		}
		now=s[now][st[i]];
	}
	return ret;
}*/
int main(){
	scanf("%lld",&n);
	ll a,b,c;
	for(ll i=1;i<n;i++){
		scanf("%lld %lld %lld",&a,&b,&c);
		if(a>b) swap(a,b);
		add(a,b,c);
	}
	dfs(1,0,0);
	cnt=0;
	ll ans=-1;
	for(ll i=1;i<=n;i++){
		ans=max(ans,insert(v[i]));
	}
	printf("%lld",ans);
	return 0;
}