2018 Multi-University Training Contest 10 - Problem E. TeaTree (樹上 dsu // 線段樹合并)

題目：http://acm.hdu.edu.cn/showproblem.php?pid=6430

題意：一棵樹上每個節點權值為v[i]，每個節點的heard值是：以它為LCA的兩個節點的GCD的最大值，要求輸出每個節點的heard值

題解：小于 100000 的數最多隻有一百多個約數. 建出所有點的約數線段樹, 然後線段樹合并, 重複的單點就可以對答案産生貢獻. 當然有省記憶體的做法, DSU on tree, 不過反正時間複雜度不變. 時間與空間都是 O(100×nlogn)。

樹上 dsu：

/**
具體的做法是，我們先計算一個點的輕兒子，再把它的影響消除。再計算重兒子，此時不必消除影響。

為了完成統計，最後再統計一遍輕兒子。

可以這麼考慮：隻有dfs到輕邊時，才會将輕邊的子樹中合并到上一級的重鍊，

樹鍊剖分将一棵樹分割成了不超過lognlogn條重鍊。
每一個節點最多向上合并lognlogn次，單次修改複雜度O(1)O(1)。
是以整體複雜度是O(nlogn)O(nlogn)的。
**/
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<map>
#include<set>
#include<vector>
using namespace std;
const int maxn = 101000;
int n,v[maxn+5],sz[maxn+5],son[maxn+5],ans[maxn+5],vis[maxn+5],mx;
vector<int>g[maxn+5],yu[maxn+5],ct;
int Map[maxn+5];
void dfsson(int x)
{
    int len = g[x].size();
    son[x] = -1;
    sz[x] = 1;
    for(int i=0,y; i<len; i++)
    {
        y = g[x][i];
        dfsson(y);
        sz[x]+=sz[y];
        if(son[x]==-1||sz[son[x]]<sz[y]) son[x] = y;
    }
}
void chang(int x,int add)
{
    int len0 = yu[v[x]].size();
    for(int i=0; i<len0; i++)
    {
        int w= yu[v[x]][i];
        if(add==1) ct.push_back(w);
        if(add==1&&Map[w]) mx = max(mx,w);
        if(add==-1) Map[w]--;
    }
    int len = g[x].size();
    for(int i=0,y; i<len; i++)
    {
        y = g[x][i];
        chang(y,add);
    }
}
void solve(int x)
{
    mx = -1;
    int len = g[x].size();
    for(int i=0,y; i<len; i++)
    {
        y = g[x][i];
        if(y==son[x]) continue;
        ct.clear();
        chang(y,1);//把輕兒子的影響加進來
        for(int j=0,l=ct.size(); j<l; j++) Map[ct[j]]++;
    }
    int len0 = yu[v[x]].size();
    for(int i=0; i<len0; i++)
    {
        int w= yu[v[x]][i];
        if(Map[w]) mx = max(mx,w);
        Map[w]++;
    }
    ans[x] = mx;
}
void dfs(int x)
{
    int len = g[x].size();
    for(int i=0,y; i<len; i++)
    {
        y = g[x][i];
        if(y==son[x]) continue;
        dfs(y);//先計算輕兒子
        chang(y,-1);//把輕兒子的影響消除
    }
    if(son[x]!=-1) dfs(son[x]);//再計算重兒子。
    solve(x);//計算x
}
int main()
{
    for(int i=1; i<=maxn; i++)
    {
        for(int j=1; j*j<=i; j++)
        {
            if(i%j) continue;
            int a = j, b = i/a;
            yu[i].push_back(a);
            if(a!=b) yu[i].push_back(b);
        }
    }
    scanf("%d",&n);
    for(int i=2,f; i<=n; i++)
    {
        scanf("%d",&f);
        g[f].push_back(i);
    }
    for(int i=1; i<=n; i++) scanf("%d",&v[i]);
    dfsson(1);
    dfs(1);
    for(int i=1; i<=n; i++) printf("%d\n",ans[i]);
    return 0;
}
           

線段樹合并：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<stdio.h>
#define mid ((l+r)>>1)
using namespace std;
typedef long long int ll;
const int maxn = 1e5;
int n,v[maxn+5];
int ls[maxn*400],rs[maxn*400],root[maxn+5],sz,ans[maxn+5];
vector<int>g[maxn+5],yu[maxn+5];
void updata(int &o,int l,int r,int p)
{
    if(o==0) o = ++sz;
    if(l==r) return;
    if(p<=mid) updata(ls[o],l,mid,p);
    if(mid<p) updata(rs[o],mid+1,r,p);
}
int Merge(int o,int pre,int l,int r,int &Mx)
{
    if(!o||!pre) return o|pre;//這裡可以比用set寫 快很多
    if(l==r) Mx = max(Mx,l);
    if(ls[o]|ls[pre]) ls[o] = Merge(ls[o],ls[pre],l,mid,Mx);
    if(rs[o]|rs[pre]) rs[o] = Merge(rs[o],rs[pre],mid+1,r,Mx);
    return o;
}
void dfs(int x)
{
    int len = g[x].size();
    ans[x] = -1;
    for(int i=0;i<len;i++)
    {
        int y = g[x][i];
        dfs(y);
        root[x] = Merge(root[x],root[y],1,maxn,ans[x]);
    }
}
int main()
{
    for(int i=1; i<=maxn; i++)
    {
        for(int j=1; j*j<=i; j++)
        {
            if(i%j) continue;
            int a = j, b = i/a;
            yu[i].push_back(a);
            if(a!=b) yu[i].push_back(b);
        }
    }
    scanf("%d",&n);
    for(int i=2,f; i<=n; i++)
    {
        scanf("%d",&f);
        g[f].push_back(i);
    }
    for(int i=1; i<=n; i++)
    {
         scanf("%d",&v[i]);
         for(int j=0,l=yu[v[i]].size();j<l;j++) updata(root[i],1,maxn,yu[v[i]][j]);
    }
    dfs(1);
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}