NIRVANA

Problem

Number

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

有$N$个正整数，需要从中选出一些数，使这些数的和最大。
若两个数$a,b$同时满足以下条件，则$a,b$不能同时被选

1. 存在正整数$c$，使$a^2+b^2=c^2$
2. $\gcd(a,b)=1$

Input

第一行一个正整数$N$，表示数的个数。
第二行$N$个正整数$a_1,a_2,\cdots ,a_N$。

Output

最大的和。

Problem

千钧一发

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

Input

第一行一个正整数$N$。
第二行共包括$N$个正整数，第 个正整数表示$A_i$。
第三行共包括$N$个正整数，第 个正整数表示$B_i$。

Output

共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。

Problem

聪聪可可

$\mathrm{Time\;Limit:\;3\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画$n$个“点”，并用$n-1$条“边”把这$n$个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是$3$的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第$1$行包含$1$个正整数$n$。后面$n-1$行，每行$3$个整数$x$、$y$、$w$，表示$x$号点和$y$号点之间有一条边，上面的数是$w$。

Output

以即约分数形式输出这个概率（即“$a/b$”的形式，其中$a$和$b$必须互质。如果概率为$1$，输出“$1/1$”）。

Problem

【IOI2011】Race

$\mathrm{Time\;Limit:\;70\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给一棵树,每条边有权.求一条简单路径,权值和等于$K$,且边的数量最小.$N\le 2\times 10^5$, $K\le 10^6$

Input

第一行 两个整数 $n, k$
第二至$n$行 每行三个整数，表示一条无向边的两端和权值 (注意点的编号从$0$开始)

Output

一个整数 表示最小边数量，如果不存在这样的路径，输出$-1$

Problem

【JOI2013】稻草人

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

$\mathrm{JOI}$村有一片荒地，上面竖着$N$个稻草人，村民们每年多次在稻草人们的周围举行祭典。
有一次，$\mathrm{JOI}$村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：

• 田地的形状是边平行于坐标轴的长方形
• 左下角和右上角各有一个稻草人
• 田地的内部（不包括边界）没有稻草人

给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数。

Input

第一行一个正整数$N$，代表稻草人的个数。
接下来$N$行，第$i$行$(1\le i\le N)$包含$2$个由空格分隔的整数$X_i$和$Y_i$，表示第$i$个稻草人的坐标。

Output

输出一行一个正整数，代表遵从启示的田地的个数。

Problem

【AMPPZ2014】The Cave

Time Limit: $5 Sec$
Memory Limit: $256 MB$
$Special Judge$

Description

给定一棵有$n$个节点的树，相邻两点之间的距离为$1$。
请找到一个点$x$，使其满足所有$m$条限制 $a\ b\ d$，其中第$i$条限制为$dist_{x,a}+dist_{x,b}\le d$

Input

第一行包含一个正整数$t$($1\le t\le 1000$)，表示数据组数。
对于每组数据，第一行包含两个正整数$n,m$($2\le n,m\le 3\times 10^5$)，表示点数、限制数。
接下来$n-1$行，每行两个正整数$x,y$($1\le x,y\le n$)，表示树上的一条边。
接下来$m$行，每行三个正整数$a[i],b[i],d[i]$($1\le a[i],b[i]\le n$, $1\le d[i]\le 6\times 10^5$)，描述一条限制。
输入数据保证所有$n$之和不超过 $3\times 10^5$，所有$m$之和也不超过 $3\times 10^5$。

Output

输出$t$行。第$i$行输出第$i$组数据的答案，如果无解输出$NIE$，否则输出$TAK$，
然后输出$x$，如有多组解，输出任意一组。

Problem

【NOIp2007】Core树网的核

Time Limit: $10 Sec$
Memory Limit: $64 MB$

Description

设$T=(V, E, W)$ 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称$T$为树网（$treenetwork$），其中$V, E$分别表示结点与边的集合，$W$表示各边长度的集合，并设$T$有$n$个结点。 路径：树网中任何两结点$a,b$都存在唯一的一条简单路径，用$d(a,b)$表示以$a,b$为端点的路径的长度，它是该路径上各边长度之和。我们称$d(a,b)$为$a,b$两结点间的距离。 一点$v$到一条路径$P$的距离为该点与$P$上的最近的结点的距离： $d(v，P)=min_{u在P上}{d(v，u)}$。 树网的直径：树网中最长的路径称为树网的直径。对于给定的树网$T$，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。 偏心距$ECC(F)$：树网$T$中距路径$F$最远的结点到路径$F$的距离，即 。 任务：对于给定的树网$T=(V, E,W)$和非负整数$s$，求一个路径$F$，它是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过$s$（可以等于$s$），使偏心距$ECC(F)$最小。我们称这个路径为树网$T=(V,E,W)$的核（$Core$）。必要时，$F$可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。 下面的图给出了树网的一个实例。图中，$A-B$与$A-C$是两条直径，长度均为$20$。点$W$是树网的中心，$EF$边的长度为$5$。如果指定$s=11$，则树网的核为路径$DEFG$（也可以取为路径$DEF$），偏心距为$8$。如果指定$s=0$（或$s=1$、$s=2$），则树网的核为结点$F$，偏心距为$12$。

Input

包含$n$行： 第$1$行，两个正整数$n$和$s$，中间用一个空格隔开。其中$n$为树网结点的个数，$s$为树网的核的长度的上界。设结点编号依次为$1, 2, \cdots, n$。 从第$2$行到第$n$行，每行给出$3$个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“$2\ 4\ 7$”表示连接结点$2$与$4$的边的长度为$7$。 所给的数据都是正确的，不必检验。

Output

只有一个非负整数，为指定意义下的最小偏心距。

Problem

Tree

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

给你一棵树以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于$K$

Input

$N$（$N\le 40000$） 接下来$n-1$行边描述管道，按照题目中写的输入 接下来是$K$

Output

一行，有多少对点之间的距离小于等于$K$

Problem

【AMPPZ2014】Petrol

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

给定一个$n$个点、$m$条边的带权无向图，其中有$s$个点是加油站。
每辆车都有一个油量上限$b$，即每次行走距离不能超过$b$，但在加油站可以补满。
$q$次询问，每次给出$x,y,b$，表示出发点是$x$，终点是$y$，油量上限为$b$，且保证$x$点和$y$点都是加油站，请回答能否从$x$走到$y$。

Input

第一行包含三个正整数$n,s,m$($2\le s\le n\le 2\times 10^5$,$1\le m\le 2\times 10^5$)，表示点数、加油站数和边数。
第二行包含$s$个互不相同的正整数$c[1],c[2],...c[s]\;(1\le c[i]\le n)$，表示每个加油站。
接下来$m$行，每行三个正整数$u[i]$,$v[i]$,$d[i]$($1\le u[i],v[i]\le n$,$u[i]\ne v[i]$,$1\le d[i]\le 10^5$)，表示$u[i]$和$v[i]$之间有一条长度为$d[i]$的双向边。
接下来一行包含一个正整数$q$($1\le q\le 2\times 10^5$)，表示询问数。
接下来$q$行，每行包含三个正整数$x[i],y[i],b[i]$($1\le x[i],y[i]\le n$,$x[i]\ne y[i]$,$1\le b[i]\le 2\times 10^9$)，表示一个询问。

Output

输出$q$行。第$i$行输出第$i$个询问的答案，如果可行，则输出$\mathrm{TAK}$，否则输出$\mathrm{NIE}$。

Problem

【AMPPZ2014】The Prices

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

你要购买$m$种物品各一件，一共有$n$家商店，你到第$i$家商店的路费为$d[i]$，在第$i$家商店购买第$j$种物品的费用为$c[i][j]$，求最小总费用。

Input

第一行包含两个正整数$n,m$($1\le n\le 100$,$1\le m\le 16$)，表示商店数和物品数。
接下来$n$行，每行第一个正整数$d[i]$($1\le d[i]\le 10^6$)表示到第$i$家商店的路费，接下来$m$个正整数，
依次表示$c[i][j]$($1\le c[i][j]< 10^6$)。

Output

一个正整数，即最小总费用。