广工2017校赛-F-- tmk找三角

http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=5

Description

有一棵树，树上有只tmk。他在这棵树上生活了很久，对他的构造了如指掌。所以他在树上从来都是走最短路，不会绕路。他还还特别喜欢三角形，所以当他在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？

Input

第一行输入一个T，表示有多少组样例。

对于每组数据：第一行包含一个整数 N，表示树上节点的个数（从 1 到 N 标号）。

接下来的 N-1 行包含三个整数 a, b, len，表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。

接下来一行包含一个整数 M，表示询问数。

接下来M行每行两个整数 S, T，表示毛毛虫从 S 爬行到了 T，询问这段路程中的树枝/树干是否能拼成三角形。

Output

对于每组数据,每个询问输出一行，包含"Yes"或“No”，表示是否可以拼成三角形。

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

No Yes No Yes

HINT

对于20%数据 1 ≤ N, M ≤ 1000

对于所有数据 1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000

一道脑洞巨大无比的题目：

假设现在有 n 条线段，假设 n 条边从小到达排序，如果这 n 条边中没有三条可以构成
三角形，那么这 n 条边必须满足关系： A[i] >= A[i-2]+A[i-1]，这里的 A[i]表示第 i 条边的大小。
假设 A[i]尽量取最小 A[i]=A[i-2]+A[i-1]，且 A[1]=A[2]=1，是不是就是一个斐波那契，也就
是对于一个 n 条边的集合，如果不存在三条边能构成一个三角形，那么最长的边至少为 f[n]，
表示斐波那契第 n 项。而题目中 A[i]<1e9，也就是只要 n>50，就必定存在三条边可以构成一
个三角形，所以我们只需要暴力加入两点路径上的边（如果大于 50，直接 Yes），然后对这
些边进行排序，枚举第 i 条边为最长边，贪心判断 A[i]是否小于 A[i-1]+A[i-2]即可

其实和这道题目是一模一样的：

http://hzwer.com/4896.html

下面的代码为了避免每次查询时都DFS一遍，使用了LCA优化了（最朴素的LCA算法）

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 100000;

int cnt = 1;

struct edge

{

    int y, val;

    int nxt;

};

edge tree[MAXN * 3];

int head[MAXN];

void addedge(int a, int b, int val)

{

    tree[cnt].y = b, tree[cnt].val = val;

    tree[cnt].nxt = head[a];

    head[a] = cnt++;

}

int dpt[MAXN], fa[MAXN],len[MAXN];

void dfs(int id)

{

    dpt[id] = dpt[fa[id]] + 1;

    int tmp = head[id];

    for (; tmp; tmp = tree[tmp].nxt) {

        if (tree[tmp].y != fa[id]) {

            fa[tree[tmp].y]=id;

            dfs(tree[tmp].y);

        }

        else{

            len[id]=tree[tmp].val;

        }

    }

    return ;

}

int e[MAXN];

int top;

bool check(int a, int b)

{

    top = 0;

    if (dpt[a] < dpt[b]) swap(a, b);

    while (dpt[a]  > dpt[b]) {

        e[++top]=len[a];

        if(top>=50)    return false;

        a=fa[a];

    }

    while(a!=b){

        e[++top]=len[a];

        e[++top]=len[b];

        if(top>=50) return false;

        a=fa[a];

        b=fa[b];

    }

    sort(e+1,e+top+1);

    for(int i=1;i<=top-2;i++){

        if(e[i]+e[i+1]>e[i+2]) return true;

    }

    return false;

}

void init()

{

    cnt=1;

    memset(dpt,0,sizeof(dpt));

    memset(head,0,sizeof(head));

    memset(fa,0,sizeof(fa));

    len[1]=0;

    fa[1]=0;

}

int main()

{

    //freopen("data.in","r",stdin);

    int t;

    int n, a, b, le;

    scanf("%d", &t);

    while (t--) {

        init();

        scanf("%d", &n);

        for (int i = 0; i < n-1; i++) {

            scanf("%d%d%d", &a, &b, &le);

            addedge(a, b, le);

            addedge(b, a, le);

        }

        dfs(1);

        int m;

        scanf("%d", &m);

        for (int i = 0; i < m; i++) {

            scanf("%d%d", &a, &b);

            if (check(a, b))

                printf("Yes\n");

            else

                printf("No\n");

        }

    }

}

巴特西