HDU6162 Ch’s gift【LCA】

제목: 나무 한 그루 를 정 하고 두 점 사이 의 경로 상의 점 권 과 점 권 은 일정한 범위 내 에서 만 유효 하 며 그렇지 않 으 면 0 이다.
사고: 처음에 T 는 양 방향 BFS 를 시 작 했 는데 나중에 LCA 라 는 알고리즘 이 생각 났 습 니 다. 안 타 깝 게 도 배 운 적 이 없습니다. 현장 학 은 템 플 릿 을 잘못 사 용 했 습 니 다. 이분 검색 으로 LCA 의 템 플 릿 을 찾 았 습 니 다.나 는 매번 새로 도착 한 점 의 권 (범위 내) 을 더 하고 이 점 을 2 점 으로 나 누 며 갱신 하 는 점 은 뛰 어 다 닌 다.한 걸음 한 걸음 위로 올 라 가 야 할 틀 로 경기 후에 야 생각 했 는데 이미 늦 었 다.
점 마다 깊이 가 있 습 니 다. 두 점 의 LCA 를 찾 을 때 여러분 은 먼저 한 깊이 로 가서 같이 위로 올 라 갑 니 다.

#include
using namespace std;
const int MAX_V = 2e5+5;
const int MAX_LOG_V = 100;
vector G[MAX_V];
int root;
int parent[MAX_V];
int dep[MAX_V];
long long ans;
long long cc[MAX_V],aa[MAX_V];

void dfs(int v,int p,int d)
{
    parent[v]=p;
    dep[v]=d;
    for(int i=0;i= c && aa[x] <= d)
        return aa[x];
    else
        return 0;
}

int lca(int u,int v,int c,int d)
{
    ans += is(u,c,d);
    ans += is(v,c,d);
    while(dep[u] > dep[v])
	{
		u = parent[u];
		ans += is(u,c,d);
	} 
	while(dep[v] > dep[u])
	{
		v = parent[v];
		ans += is(v,c,d);
	}
	while(u != v)
	{
		u = parent[u];
		ans += is(u,c,d);
		v = parent[v];
		ans += is(v,c,d);
	}
	ans -= is(v,c,d);
	return u;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
    	for(int i = 0; i <= n; i++)
    		G[i].clear();
        root = n / 2;
        for(int i = 0; i < n; i++)
            scanf("%lld",&aa[i]);
        for(int i = 1; i < n; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            a--;b--;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        init(n);
        for(int i = 1; i <= m; i++)
        {
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            a--;b--;
            ans = 0;
            lca(a,b,c,d);
            cc[i] = ans;
        }
        for(int i = 1; i <= m; i++)
            printf("%lld%c",cc[i],i==m?'
':' ');
    }
    return 0;
}