- 首页 > it技术 > >
数学方法|广东工业大学新生赛决赛F题
// by BNU_LZM
#include
#include
#include
#include
using namespace std;
const int maxn = 100000+5;
struct Edge
{
int u, v, d;
Edge(int u, int v, int d) : u(u), v(v), d(d) {}
};
vector edges;
vector G[maxn];
int n, dep[maxn], dis[maxn], f[maxn];
void dfs(int u, int d)
{
dep[u] = d;
for(int i = 0;
i < G[u].size();
i++)
{
Edge &e = edges[G[u][i]];
int v = e.v;
if(v == f[u]) continue;
dis[v] = e.d;
f[v] = u;
dfs(v, d+1);
}
}bool solve(int a, int b)
{
vector aa;
while(a != b)
{
if(aa.size() >= 50) return true;
if(dep[a] > dep[b])
{
aa.push_back(dis[a]);
a = f[a];
}
else
{
aa.push_back(dis[b]);
b = f[b];
}
}
if(aa.size() < 3) return false;
sort(aa.begin(), aa.end());
for(int i = 0;
i < aa.size()-2;
i++)
{
if(aa[i]+aa[i+1] > aa[i+2]) return true;
}
return false;
}int main()
{
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while(T--)
{
edges.clear();
for(int i = 1;
i <= n;
i++) G[i].clear();
scanf("%d", &n);
for(int i = 1;
i < n;
i++)
{
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
edges.push_back(Edge(u, v, d));
G[u].push_back(edges.size()-1);
edges.push_back(Edge(v, u, d));
G[v].push_back(edges.size()-1);
}
memset(f, -1, sizeof(f));
dfs(1, 0);
int m;
scanf("%d", &m);
for(int i = 1;
i <= m;
i++)
{
int a, b;
scanf("%d%d", &a, &b);
if(solve(a, b)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
推荐阅读
