Time Limit: 5 Sec  Memory Limit: 256 MBSec  Special Judge

Submit: 293  Solved: 144

[][][]

Description

给定一棵有n个节点的树，相邻两点之间的距离为1。

请找到一个点x，使其满足所有m条限制，其中第i条限制为dist(x,a[i])+dist(x,b[i])<=d[i]。

Input

第一行包含一个正整数t(1<=t<=1000)，表示数据组数。

对于每组数据，第一行包含两个正整数n,m(2<=n,m<=300000)，表示点数、限制数。

接下来n-1行，每行两个正整数x,y(1<=x,y<=n)，表示树上的一条边。

接下来m行，每行三个正整数a[i],b[i],d[i](1<=a[i],b[i]<=n,1<=d[i]<=600000)，描述一条限制。

输入数据保证所有n之和不超过300000，所有m之和也不超过300000。

Output

输出t行。第i行输出第i组数据的答案，如果无解输出NIE，否则输出TAK，

然后输出x，如有多组解，输出任意一组。

Sample Input

2

5 3

1 2

2 3

2 4

3 5

1 4 2

5 5 5

3 2 1

3 2

1 2

2 3

1 1 2

3 3 1

Sample Output

TAK 2

NIE

HINT

Source

鸣谢Claris上传

 

题解：

        ①首先呢要搞懂：(设1为根)

               满足第i个限制条件：dist(x,a[i])+dist(x,b[i])<=d[i] 的所有点中，

               离根节点最近的点的到达根的距离D是有一个公式的： 

                D=max(   0   ,   (dis(a[i],1) + dis(b[i],1) - d[i]) / 2    )

                [温馨提示：画个图走一波就可以懂]

        ②然后呢，根据上文结论呢，设 D 值 最大的点时 P。

               有一个更高级的结论：如果P都不能合法，那么没有什么点会合法了。

        ③插几句，怎么找到P点：

                      根据P点必须满足最苛刻的条件，可以从对应的a[i],b[i]为根遍历树得到dis[],

                      然后呢找到满足最苛刻条件，且到1最近的那个点就是我们D对应的P点了。

        ④我是这样理解这个结论的：

                      (1)P点的位置是由最苛刻的限制条件得出的(即离根最远)

                      (2)对于和它统一棵子树的限制条件，肯定他可以满足所有(因为他是最苛刻的)

                      (3)对于和它不在同一子树的限制条件，也必须想办法满足它才可以。

#include
    
     #include
     
      #define go(i,a,b) for(int i=a;i<=b;i++)#define mem(a,b) memset(a,b,sizeof(a))#define fo(i,a,x) for(int i=a[x],v=e[i].v;i;i=e[i].next,v=e[i].v)const int N=400010;struct E{int v,next;}e[N<<1];int T,n,m,i,x,y,t,ed,a[N],b[N],d[N],D[3][N],k,head[N];void ADD(int u,int v){e[k]=(E){v,head[u]};head[u]=k++;}void dfs(int u,int fa,int z,int p){   	D[p][x]=z++;	fo(i,head,u)if(v!=fa)dfs(v,u,z,p);}int main(){	scanf("%d",&T); 	while(T--&&scanf("%d%d",&n,&m))	{    	go(i,1,n)head[i]=0;k=1;    	go(i,2,n){int u,v;scanf("%d%d",&u,&v),ADD(u,v),ADD(v,u);}    	go(i,1,m)scanf("%d%d%d",a+i,b+i,d+i);    	dfs(1,0,0,0);x=0;		go(i,1,m)    	{      		t=D[0][a[i]]+D[0][b[i]]-d[i];      		if(!x||t>y)x=i,y=t;    	}    	dfs(a[x],0,0,1),dfs(b[x],0,0,2);t=0;    	go(i,1,n)if(D[1][i]+D[2][i]<=d[x])if(!t||D[0][i]
      
       d[i]){t=0;break;}    	if(t)printf("TAK %d\n",t);else puts("NIE");   }   return 0;}//Paul_Guderian
      
     
    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

外面下起了小雨,雨滴轻飘飘得像我的年轻岁月，

我脸上蒙着雨水就像蒙着幸福……——————————汪峰《青春》