#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 200010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to; }edge[N<<1]; int cnt=1,head[N]; void add(int from,int to) { edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt++; } int d1[N],dn[N]; void dfs1(int x,int fa) { for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(to==fa)continue; d1[to]=d1[x]+1; dfs1(to,x); } } void dfsn(int x,int fa) { for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(to==fa)continue; dn[to]=dn[x]+1; dfsn(to,x); } } int n,T; int main() { //freopen("book.in","r",stdin); //freopen("book.out","w",stdout); T=read(); while(T--) { cnt=1; memset(head,0,sizeof(head)); n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); add(u,v),add(v,u); } dfs1(1,0),dfsn(n,0); int cnt1=0,cntn=0; for(int i=1;i<=n;i++) { if(d1[i]<=dn[i])cnt1++; else cntn++; } if(cnt1>cntn)puts("^_^"); else puts("T_T"); } }
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 200010 #define ll long long using namespace std; struct star { int to; int next; }edge[100001]; int n,t,cnt; int head[100001]; int df1[100001],df2[100001]; void add(int u,int v) { edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs1(int a,int b) { int i,to; for(i=head[a];~i;i=edge[i].next) { to=edge[i].to; if(to==b) continue; df1[to]=df1[a]+1; dfs1(to,a); } } void dfs2(int a,int b) { int i,to; for(i=head[a];~i;i=edge[i].next) { to=edge[i].to; if(to==b) continue; df2[to]=df2[a]+1; dfs2(to,a); } } int main() { int u,v; cin>>t; while(t--) { int i,j,temp1=0,temp2=0; cin>>n; memset(head,-1,sizeof(head)); cnt=1; for(i=1;i<=n-1;i++){cin>>u>>v;add(u,v);add(v,u);} dfs1(1,0);dfs2(n,0); for(i=1;i<=n;i++) { if(df1[i]<df2[i]) temp1++; else temp2++; } if(temp1>temp2) cout<<"^_^"<<endl; else cout<<"T_T"<<endl; } return 0; }
60