Tree
Problem Description
wls 有三棵树，树上每个节点都有一个值 ai，现在有 2 种操作：
- 将一条链上的所有节点的值开根号向下取整；
- 求一条链上值的和；
链的定义是两点之间的最短路。
Input
第一行两个数 n, q 分别代表树上点的数量和操作数量。
第二行 n 个整数，第 i 个数代表第 i 个点的值 ai。
接下来 n − 1 行， 每行两个整数 u, v 代表 u，v 之间有一条边。数据保证点两两联通。
接下来 q 行，每行有个整数 op, u, v，op = 0 表示将 u, v 这条链上所有的点的值开根号向下取整，op = 1表示询问 u，v 这条链上的值的和。
1 ≤ n, q ≤ 100, 000
0 ≤ ai ≤ 1, 000, 000, 000
Output
对于每一组 op = 2 的询问，输出一行一个值表示答案。
Sample Input
4 4
2 3 4 5
1 2
2 3
2 4
0 3 4
0 1 3
1 2 3
1 1 4
Sample Output
2
4
Source
2019中国大学生程序设计竞赛-女生专场（重现赛）-感谢南京晓庄学院
HINT
用动态数组存 思路简单 一个树的结构。然后进行操作。如果原理搞不懂先去学学数据结构比较好理解。
Code：
#include<bits/stdc++.h>
using namespace std;
const int maxx=100010;
struct node
{
int nt,w;
};
vector<node>v[maxx];
bool book[maxx];
int pre[maxx],dth[maxx],val[maxx],qwq[maxx];
int dfs(int x)
{
book[x]=1;
for(int i=0;i<v[x].size();i++)
{
if(book[v[x][i].nt])continue;
pre[v[x][i].nt]=x;
dth[v[x][i].nt]=dth[x]+1;
dfs(v[x][i].nt);
}
}
int f(int x,int y,int op)
{
int cnt=0,flag=0;
while(x!=y)
{
if(dth[x]>=dth[y])
{
qwq[cnt++]=x;
x=pre[x];
flag=0;
}else
{
qwq[cnt++]=y;
y=pre[y];
flag=1;
}
}
if(flag==0)qwq[cnt++]=x;
else qwq[cnt++]=x;
if(op==0)
{
for(int i=0;i<cnt;i++)
val[qwq[i]]=sqrt(val[qwq[i]]);
}else
{
long long sum=0;
for(int i=0;i<cnt;i++)
sum+=val[qwq[i]];
printf("%lld\n",sum);
}
return 0;
}
int main()
{
int n,q;
scanf("%d %d",&n,&q);
int x,y;
node a;
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
for(int i=0;i<n-1;i++)
{
scanf("%d %d",&x,&y);
a.nt=y;
v[x].push_back(a);
a.nt=x;
v[y].push_back(a);
}
dfs(1);
for(int i=0;i<q;i++)
{
int x,y,op;
scanf("%d %d %d",&op,&x,&y);
f(x,y,op);
}
return 0;
}
Saber
Time Limit: 2 Seconds Memory Limit: 65536 KB
Saber is a Class in the Holy Grail War. This Class is regarded as one of the most powerful Class.
Saber is a tree-lover. She loves all kinds of trees. One day, she suddenly comes up with a curious problem. She wants to know that in the path between x and y, whether it exists that when we choose three different edges i,j,k, the length of these three edges can build a triangle. Now she wants you to solve this problem.
Input
There are multiple test cases. The first line of input contains an integer T(T ≤ 5), indicating the number of test cases. For each test case:
The first line contains one integer N(1 ≤ N ≤ 100000), indicating the number of tree’s vertices. In the following N-1 lines, there are three integers x, y, w (1 ≤ w ≤ 1000000000), indicating an edge weighted w between x and y.
In the following line also contains one integer Q(1 ≤ Q ≤ 100000), indicating the number of queries. In the following Q lines, there are two integers x, y, indicating a query between x and y.
Output
For each test case output ‘Case #i:’ in the first line, i equals to the case number. Then for every query output ‘Yes’ or ‘No’ in one line.
Sample Input
2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
2
1 4
1 3
Sample Output
Case #1:
No
Yes
Case #2:
No
Yes
Code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
struct node
{
int nt,w;
};
vector<node>v[maxn];
bool book[maxn];
int dth[maxn],val[maxn],pre[maxn];
int qwq[55];
void dfs(int x)
{
book[x]=1;
for(int i=0; i<v[x].size(); i++)
{
if(book[v[x][i].nt])
continue;
pre[v[x][i].nt]=x;
dth[v[x][i].nt]=dth[x]+1;
val[v[x][i].nt]=v[x][i].w;
dfs(v[x][i].nt);
}
}
int f(int x,int y)
{
int cnt=0;
while(x!=y)
{
if(cnt>=50)
return 1;
else
{
if(dth[x]>=dth[y])
{
qwq[cnt++]=val[x];
x=pre[x];
}
else
{
qwq[cnt++]=val[y];
y=pre[y];
}
}
}
sort(qwq,qwq+cnt);
for(int i=0; i<cnt-2; i++)
{
if(qwq[i]+qwq[i+1]>qwq[i+2])
return 1;
}
return 0;
}
int main()
{
int t,n;
scanf("%d",&t);
int ca=0;
while(t--)
{
memset(book,0,sizeof(book));
printf("Case #%d:\n",++ca);
scanf("%d",&n);
for(int i=0; i<=n; i++)
v[i].clear();
int x,y,w;
node a;
for(int i=1; i<n; i++)
{
scanf("%d%d%d",&x,&y,&w);
a.nt=y;
a.w=w;
v[x].push_back(a);
a.nt=x;
a.w=w;
v[y].push_back(a);
}
dfs(1);
int q;
scanf("%d",&q);
while(q--)
{
int qx,qy;
scanf("%d%d",&qx,&qy);
if(qx>qy)
swap(qx,qy);
int f1=0;
f1=f(qx,qy);
printf(f1?"Yes\n":"No\n");
}
}
return 0;
}