小睿睿的伤害

C++(g++ 7.5.0) 解法, 执行用时: 330ms, 内存消耗: 28044K, 提交时间: 2022-08-05 22:46:14

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;

ll sz[maxn],son[maxn],mx[maxn],num[maxn],cnt[maxn];
ll n,a,u,v,w;
vector<int>ed[maxn],vt[maxn];

void dfs(int x,int fa)
{
	sz[x]=1;
	for(auto y:ed[x])
	{
		if(y==fa)continue;
		dfs(y,x); sz[x]+=sz[y];
		if(sz[son[x]]<sz[y])son[x]=y;
	}
	return;
}


void del(int x,int fa, int flag)
{
	for(auto y:vt[x])cnt[y] += flag;
	for(auto y:ed[x])
		if(y!=fa)del(y,x, flag);
	return;
}

void cal(int x,int p)
{
	for(auto y:vt[x])
	{
		if(mx[p]<y&&cnt[y])
		{
			mx[p]=y; num[p]=cnt[y];
		}
		else if(mx[p]==y)num[p]+=cnt[y];
	}
	return;
}

void calcu(int x,int fa,int p)
{
	cal(x,p);
	for(auto y:ed[x])
		if(y!=fa)calcu(y,x,p);
	return;
}

void solve(int x,int fa,int kp)
{
	for(auto y:ed[x])
	{
		if(y==fa||y==son[x])continue;
		solve(y,x,0);
	}
	if(son[x])solve(son[x],x,1),cal(x,x);
	for(auto y:vt[x])cnt[y]++;
	for(auto y:ed[x])
	{
		if(y==fa||y==son[x])continue;
		calcu(y,x,x); del(y, x, 1);
	}
	if(!kp)del(x,fa, -1);
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		ed[u].push_back(v);
		ed[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		for(int j=1;j*j<=a;j++)
		{
			if(a%j==0)
			{
				vt[i].push_back(j);
				if(j*j!=a)vt[i].push_back(a/j);
			}
		}
	}
	dfs(1,0); solve(1,0,1);
	for(int i=1;i<=n;i++)
	{
		cout<<mx[i]<<" "<<num[i]<<"\n"; 
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 558ms, 内存消耗: 69060K, 提交时间: 2020-08-22 15:41:16

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
int n, val[maxn];
vector<int> g[maxn];
map<int,int> mp[maxn];
ll ans[maxn], cnt[maxn];
void dfs(int x, int fx) {
    for (int i = 1; i * i <= val[x]; i++) {
        if(val[x] % i == 0) {
            mp[x][i]++;
            if(val[x] / i != i) mp[x][val[x] / i]++;
        }
    }
    for (auto v : g[x]) {
        if(v == fx) continue;
        dfs(v, x);
        if(mp[v].size() > mp[x].size()) swap(mp[v], mp[x]);
        for (auto j : mp[v]) {
            if(mp[x].count(j.first)) {
                if(ans[x] == j.first) {
                    cnt[x] += (ll)mp[x][j.first] * j.second;
                }
                if(ans[x] < j.first) {
                    ans[x] = j.first;
                    cnt[x] = (ll)mp[x][j.first] * j.second;
                }
            }
            mp[x][j.first] += j.second;
        }
        mp[v].clear();
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1, a, b; i < n; i++) {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &val[i]);
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        printf("%lld %lld\n", ans[i], cnt[i]);
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 610ms, 内存消耗: 70520K, 提交时间: 2020-08-22 10:41:30

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=1e5+10;

map<int,int> mp[maxn];
int val[maxn];
ll ans[maxn],cnt[maxn];
int a[maxn];
vector<int> g[maxn];

void dfs( int x,int f )
{
	for( int i=1;i*i<=a[x];i++ )
	{
		if( a[x]%i==0 )
		{
			mp[x][i]++;
			if( a[x]/i!=i ) mp[x][a[x]/i]++;
		}
	}
	
	for( int v:g[x] )
	{
		if( v==f ) continue;
		dfs(v,x);
		if( mp[v].size()>mp[x].size() ) swap(mp[v],mp[x]);
		for( auto l:mp[v] )
		{
			if( mp[x].count(l.first) )
			{
				if( ans[x]==l.first ) cnt[x]+=1ll*l.second*mp[x][l.first];
				else if( ans[x]<l.first )
				{
					ans[x]=l.first;
					cnt[x]=1ll*l.second*mp[x][l.first];
				}
			}
			mp[x][l.first]+=l.second;
		}
		mp[v].clear();
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	for( int i=0;i<n-1;i++ )
	{
		int a,b;
		scanf("%d%d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for( int i=1;i<=n;i++ ) scanf("%d",&a[i]);
	dfs(1,0);
	for( int i=1;i<=n;i++ )
	{
		printf("%lld %lld\n",ans[i],cnt[i]);
	}
}

详情